Note that a string S_{2i} is a string S_i in which each character is repeated twice. We leave the proof to the reader.

Now, we can find the desired string recursively. String S_ {2k}[2l+0..1,2r+0..1] can be calculated by

duplicating the characters of the string S_k[l\pm 1, r\pm 1]. String S_{2k+1}[l,r] can be calculated by directly performing a single operation on the string S_{2k}[l-1,r+1].

Resulting complexity is O(n \log k + \sum (r - l + 1))