For convenience, we interpret “executing a program consisting of a \(k\)-time concatenation of string \(S\)” as “executing string \(S\) for \(K\) times.”

Let us denote by \((0, 0) \rightarrow (x_1, y_1) \rightarrow (x_2, y_2) \rightarrow \cdots \rightarrow (x_{|S|}, y_{|S|})\) the transitions of Robot’s position. Here, \(|S|\) denotes the length of \(S\).
Let \(a, b\) be \(x_{|S|}, y_{|S|}\), respectively.

Let \(V_1\) be a set of squares which robot visits during the first time of execution (including the initial position before the first execution \((0, 0)\)). In other words, \(V_1\) is a set consisting of \((0, 0), (x_1, y_1), (x_2, y_2), \cdots, (x_{|S|}, y_{|S|})\), without duplicates. Let us arbitrarily number the elements of \(V_1\), denoting

\(V_1 = \lbrace (X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N) \rbrace\).

Here, \(N\) is the number of elements of \(V_1\).
Then, set \(V_2\), the set of squares which robot visits during the second time of execution (including the initial position before the second execution), can be obtained by shifting each element of \(V_1\) by \((a, b)\):

\(V_2 = \lbrace (X_1 + a, Y_1 + b), (X_2 + a, Y_2 + b), \ldots, (X_N + a, Y_N + b) \rbrace\).

Set \(V_3\), the set of squares which robot visits during the third time of execution (including the initial position before the third execution), can be obtained by again shifting each element of \(V_2\) by \((a, b)\):

\(V_3 = \lbrace (X_1 + 2a, Y_1 + 2b), (X_2 + 2a, Y_2 + 2b), \ldots, (X_N + 2a, Y_N+ 2b) \rbrace\).

Generally, set \(V_k\), the set of squares which robot visits during the \(K\)-th time of execution (including the initial position before the \(K\)-th execution), can be represented as:

\(V_k = \lbrace (X_1 + (k-1)a, Y_1 + (k-1)b), (X_2 + (k-1)a, Y_2 + (k-1)b), \ldots, (X_N + (k-1)a, Y_N+ (k-1)b) \rbrace\).

Especially note that, for \(i = 1, 2, \ldots, N\), \((X_i, Y_i) \in V_1\) corresponds to:

• \((X_i + a, Y_i + b)\) for the second execution;
• \((X_i + 2a, Y_i + 2b)\) for the third execution;
• \(\cdots\)
• \((X_i + (k-1)a, Y_i + (k-1)b)\) for the \(k\)-th execution.

Here, for \(i = 1, 2, \ldots, N\), let

\(d_i\) := （minimum integer \(j\) such that \((X_i+ja, Y_i+jb) \in V_1\)）

If there does not exist such integer \(j\), we define \(d_i := \infty\).

Then, focusing \((X_i, Y_i) \in V_1\), as for the first \(d_i\) executions,

• it visits Square \((X_i, Y_i)\) for the first time during the first execution;
• it visits Square \((X_i + a, Y_i + b)\) for the first time during the second execution;
• it visits Square \((X_i + 2a, Y_i + 2b)\) for the first time during the third execution;
• \(\cdots\)
• it visits Square \((X_i + (d_i-1)a, Y_i + (d_i-1)b)\) for the first time during the \(d_i\)-th execution.

However, for \((d_i+1)\)-th execution and later,

• it visits Square \((X_i + d_ia, Y_i + d_ib)\) during the \((d_i+1)\)-th execution, but this is not his first visit there.
  (By the definition of \(d_i\), \((X_i + d_ia, Y_i + d_ib) \in V_1\), so it already visited during the first execution)
• it visits Square \((X_i + (d_i+1)a, Y_i + (d_i+1)b)\) during the \((d_i+2)\)-th execution, but this is not his first visit there.
  (\((X_i + (d_i+1)a, Y_i + (d_i+1)b) = ((X_i+d_ia) + a, (Y_i+d_ib) + b)\), so it already visited during the second execution)
• it visits Square \((X_i + (d_i+2)a, Y_i + (d_i+2)b)\) during the \((d_i+3)\)-th execution, but this is not his first visit there.
  (\((X_i + (d_i+2)a, Y_i + (d_i+2)b) = ((X_i+d_ia) + 2a, (Y_i+d_ib) + 2b)\), so it already visited during the third execution)
• \(\cdots\)

and so on.
Therefore, while executing \(S\) for \(K\) times, this \((X_i, Y_i)\) changes an unvisited square to a visited one \(\min(d_i, K)\) times.

Therefore, the answer for this problem is

\(\displaystyle\sum_{i = 1}^N \min(d_i, K)\).

Thus, this problem boils down to finding \(d_i\) for all \(i = 1, 2, \ldots, N\). We will explain how to do it.

If \(a = b = 0\), we can see that \(d_1 = d_2 = \cdots = d_N = 1\). Also, if \(a = 0, b \neq 0\), we can swap the role of \(X\) coordinates and \(Y\) coordinates to assume that \(a \neq 0\), so we hereinafter assume \(a \neq 0\).

First, for each \(i = 1, 2, \ldots, N\), we calculate

\(q_i = \left\lfloor \displaystyle\frac{X_i}{a} \right\rfloor\)

\(s_i = X_i - q_i a\)

\(t_i = Y_i - q_i b\),

and group the elements of \(V_i\) depending on \((s_i, t_i)\). ( We define that \((X_i, Y_i)\) and \((X_j, Y_j)\) belongs to the same group if and only if \((s_i, t_i) = (s_j, t_j)\).)

For any \(1 \leq i, j \leq N\),

\((s_i, t_i) = (s_j, t_j) \Leftrightarrow (X_j, Y_j) = (X_i + (q_j-q_i)a, Y_i + (q_j-q_i)b)\),

so by sorting the elements of each group by \(q_i\), we can “find the value of \(d_i\) for each \(i = 1, 2, \ldots, N\) in a total of \(\mathrm{O}(|S|\log|S|)\) time.”

Therefore, we can solve this problem in a total of \(\mathrm{O}(|S|\log|S|)\) time.