This is an implementation problem, therefore most of the solution fit in the time limit. We can even save the keyboard in 3 strings and make a brute force search for each character to find its position and then print the left/right neighbour.

There are two solutions:

We can make partial sums (

*sum*_{i}=*a*_{1}+*a*_{2}+ ... +*a*_{i}) and then make a binary search for each query*q*_{i}to find the result*j*with the properties*sum*_{j - 1}<*q*_{i}and*sum*_{j}≥*q*_{i}. This solution has the complexity*O*(*n*+*m*·*log*(*n*))We can precalculate the index of the pile for each worm and then answer for each query in

*O*(1). This solution has the complexity*O*(*n*+*m*)

For each 4 points we want to see if we can rotate them with 90 degrees such that we obtain a square. We can make a backtracking where we rotate each point 0, 1, 2 or 3 times and verify the figure obtained. If it's a square we update the minimal solution. Since we can rotate each point 0, 1, 2 or 3 times, for each regiment we have 4^{4} configurations to check. So the final complexity is about *O*(*n*).

We can notate each string as a binary string, instead of red and white flowers. A string of this type is good only if every maximal contigous subsequence of "0" has the length divisible by *k*. We can make dynamic programming this way : *nr*_{i} = the number of good strings of length *i*. If the *i*-th character is "1" then we can have any character before and if the *i*-th character is "0" we must have another *k* - 1 "0" characters before, so *nr*_{i} = *nr*_{i - 1} + *nr*_{i - k} for *i* ≥ *k* and *nr*_{i} = 1 for *i* < *k*. Then we compute the partial sums (*sum*_{i} = *nr*_{1} + *nr*_{2} + ... + *nr*_{i}) and for each query the result will be *sum*_{b} - *sum*_{a - 1}. This solution has the complexity *O*(*maxVal* + *t*), where *maxVal* is the maximum value of *b*_{i}.

We have to find a substring *i*_{1}, *i*_{2}, ..., *i*_{k} such that *abs*(*h*_{ij} - *h*_{ij + 1}) ≥ *D* for 1 ≤ *j* < *k*. Let's suppose that the values in *h* are smaller. We can make dynamic programming this way : *best*_{i} = the maximal length of such a substring ending in the *i*-th position, *best*_{i} = *max*(*best*_{j}) + 1 with *j* < *i* and *h*_{j} ≥ *D* + *h*_{i} or *h*_{j} ≤ *h*_{i} - *D*. So we can easily search this maximum in a data structure, such as an segment tree or Fenwick tree. But those data structure must have the size of *O*(*maxH*) which can be 10^{9}. For our constraints we mantain the idea described above, but instead of going at some specific position in the data structure based on a value, we would normalize the values in *h* and binary search the new index where we should go for an update or a query in the data structure. Therefore, the data structure will have the size *O*(*n*). The complexity of this solution is *O*(*n*·*log*(*n*)).

For each subsequence [*L*, *R*] we must find how many queens we have. A value is "queen" only if is the GCD of (*s*_{L}, *s*_{L + 1}, ..., *s*_{R}). Also, we must notice that the GCD of (*s*_{L}, *s*_{L + 1}, ..., *s*_{R}) can be only the minimum value from (*s*_{L}, *s*_{L + 1}, ..., *s*_{R}). So for each query we search in a data structure (a segment tree or a RMQ) the minimum value and the GCD of (*s*_{L}, *s*_{L + 1}, ..., *s*_{R}) and if these two values are equal then we output the answer *R* - *L* + 1 - *nrValues*, where *nrValues* is the number of values in the subsequence equal to the GCD and the minimum value. The complexity of this solution is *O*(*n*·*log*(*n*)·*log*(*valMax*) + *t*·*log*(*n*)·*log*(*valMax*)), where *valMax* is the maximum value of *s*_{i}.