Firstly, let us notice that changing the word direction from row to row doesn't have any impact on the number of individual letters in a certain row.

A naive solution would be to simulate writing the letters into each row and count the number of appearances of individual letters in the matrix ~num[26][N]~ and then output the value from the matrix for each query. The memory complexity of this solution is ~\mathcal O(N)~ and time complexity ~\mathcal O(N^2+K)~, which is enough for ~50\%~ of total points.

For a more effective solution, we need to examine how string ~s~ looks written down in each row. There are two options:

1. ~s = w[i \dots j]~ for some ~i~ and ~j~. In other words, string ~s~ is a substring of string ~w~.
2. ~s = w[i \dots L] + x \times w + w[0 \dots j]~ for some ~i~ and ~j~. In other words, string ~s~ consists of a suffix of string ~s~ (possibly an empty one), then the whole word ~w~ repeated ~x~ times and, finally, a suffix of string ~w~ (possibly an empty one)

For example, if the word ~w~ would be ~\text{ABCD}~, the ~12^\text{th}~ row of the pyramid would be:

$$\displaystyle \text{CDABCDABCDAB} = \text{CD} + 2 \times \text{ABCD} + \text{AB} = w[2 \dots 4] + 2 \times w + w[0 \dots 2]$$

In order to determine ~x~, ~i~ and ~j~ for a certain row, we need to be able to determine what letter the word in that row begins with. It is easily shown that for row ~r~ that position is equal to the remainder of dividing number ~r(r-1)/2~ with ~m~. It is necessary to carefully implement this formula because ~r~ can be very big. When we have calculated the position, it is easy to determine parameters ~x~, ~i~ and ~j~.

Now we can come up with the formulas for certain cases. Let ~f(c, i, j)~ be the number of appearances of ~c^\text{th}~ letter of the alphabet in the substring ~w[i \dots j]~. The formulas are the following:

1. ~\text{number_of_appearances} = f(c, i, j)~
2. ~\text{number_of_appearances} = f(c, i, L) + x \times f(c, 0, L) + f(c, 0, j)~

To implement this solution effectively, we need to be able to quickly calculate the value of function ~f~. We can do this by constructing a matrix ~p[26][L]~ where the element at index ~[i][j]~ tells us how many times the ~i^\text{th}~ letter of the alphabet appears in the substring ~w[0 \dots j]~. Then we calculate ~f(c, i, j)~ by the formula ~f(c, i, j) = p[c][j]-p[c][i-1]~.

The memory complexity of this solution is ~\mathcal O(M)~, and time complexity ~\mathcal O(M+K)~, which was enough for all the points in HONI.

In COCI, this solution was enough for ~70\%~ of total points because the maximal string length was bigger, so a matrix of the dimension ~26L~ couldn't fit in 32 MB. It was necessary to solve queries separately for each letter. In this case, instead of a matrix of the dimension ~26L~, a matrix of the dimension ~L~ was enough.