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\mathrm{\%}$ 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\mathrm{\%}$ 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.