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 (sumi = a1 + a2 + ... + ai) and then make a binary search for each query qi to find the result j with the properties sumj - 1 < qi and sumj ≥ qi. 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 44 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 : nri = 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 nri = nri - 1 + nri - k for i ≥ k and nri = 1 for i < k. Then we compute the partial sums (sumi = nr1 + nr2 + ... + nri) and for each query the result will be sumb - suma - 1. This solution has the complexity O(maxVal + t), where maxVal is the maximum value of bi.
We have to find a substring i1, i2, ..., ik such that abs(hij - hij + 1) ≥ D for 1 ≤ j < k. Let's suppose that the values in h are smaller. We can make dynamic programming this way : besti = the maximal length of such a substring ending in the i-th position, besti = max(bestj) + 1 with j < i and hj ≥ D + hi or hj ≤ hi - 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 109. 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 (sL, sL + 1, ..., sR). Also, we must notice that the GCD of (sL, sL + 1, ..., sR) can be only the minimum value from (sL, sL + 1, ..., sR). So for each query we search in a data structure (a segment tree or a RMQ) the minimum value and the GCD of (sL, sL + 1, ..., sR) 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 si.
