P13213 [GCJ 2015 Qualification] Dijkstra

The Dutch computer scientist Edsger Dijkstra made many important contributions to the field, including the shortest path finding algorithm that bears his name. This problem is not about that algorithm. You were marked down one point on an algorithms exam for misspelling "Dijkstra" -- between d and stra, you wrote some number of characters, each of which was either $i, j$, or $k$. You are prepared to argue to get your point back using quaternions, an actual number system (extended from complex numbers) with the following multiplicative structure: | | $1$ | $i$ | $j$ | $k$ | |:---:|:---:|:---:|:---:|:---:| | $1$ | $1$ | $i$ | $j $| $k$ | | $i$ | $i$ | $-1$ | $k$ | $-j$ | | $j$ | $j$ | $-k$ | $-1$ | $i$ | | $k$ | $k$ | $j$ | $-i$ | $-1$ | To multiply one quaternion by another, look at the row for the first quaternion and the column for the second quaternion. For example, to multiply $i$ by $j$, look in the row for $i$ and the column for $j$ to find that the answer is $k$. To multiply $j$ by $i$, look in the row for $j$ and the column for $i$ to find that the answer is $-k$. As you can see from the above examples, the quaternions are not commutative -- that is, there are some $\mathbf{a}$ and $\mathbf{b}$ for which $\mathbf{a} \times \mathbf{b} \neq \mathbf{b} \times \mathbf{a}$. However they are associative -- for any $\mathbf{a}$, $\mathbf{b}$, and $\mathbf{c}$, it's true that $\mathbf{a} \times (\mathbf{b} \times \mathbf{c}) = (\mathbf{a} \times \mathbf{b}) \times \mathbf{c}$. Negative signs before quaternions work as they normally do -- for any quaternions $\mathbf{a}$ and $\mathbf{b}$, it's true that $-\mathbf{a} \times -\mathbf{b} = \mathbf{a} \times \mathbf{b}$, and $-\mathbf{a} \times \mathbf{b} = \mathbf{a} \times -\mathbf{b} = -(\mathbf{a} \times \mathbf{b})$. You want to argue that your misspelling was equivalent to the correct spelling `ijk` by showing that you can split your string of `i`s, `j`s, and `k`s in two places, forming three substrings, such that the leftmost substring reduces (under quaternion multiplication) to $i$, the middle substring reduces to $j$, and the right substring reduces to $k$. (For example, `jij` would be interpreted as $j \times i \times j$; $j \times i$ is $-k$, and $-k \times j$ is $i$, so `jij` reduces to $i$.) If this is possible, you will get your point back. Can you find a way to do it?

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each consists of one line with two space-separated integers $\mathbf{L}$ and $\mathbf{X}$, followed by another line with $\mathbf{L}$ characters, all of which are $\mathbf{i}$, $\mathbf{j}$, or $\mathbf{k}$. Note that the string never contains negative signs, 1s, or any other characters. The string that you are to evaluate is the given string of $\mathbf{L}$ characters repeated $\mathbf{X}$ times. For instance, for $\mathbf{L} = 4$, $\mathbf{X} = 3$, and the given string $\mathbf{kiiij}$, your input string would be $\mathbf{kiijkiijkiij}$.

For each test case, output one line containing `Case #x: y`, where $\mathbf{x}$ is the test case number (starting from 1) and $\mathbf{y}$ is either $\mathbf{yes}$ or $\mathbf{no}$, depending on whether the string can be broken into three parts that reduce to $i$, $j$, and $k$, in that order, as described above.

**Sample Explanation** In Case #1, the string is too short to be split into three substrings. In Case #2, just split the string into i, j, and k. In Case #3, the only way to split the string into three parts is k, j, i, and this does not satisfy the conditions. In Case #4, the string is $\mathbf{jijijijijiji}$. It can be split into $\mathbf{jij}$ (which reduces to i), $\mathbf{iji}$ (which reduces to j), and $\mathbf{jijiji}$ (which reduces to k). In Case #5, no matter how you choose your substrings, none of them can ever reduce to a j or a k. **Sample Explanation** - $1 \leq \mathbf{T} \leq 100$. - $1 \leq \mathbf{L} \leq 10000$. **Small dataset(11 Pts)** - Time limit: ~~240~~ 5 seconds. - $1 \leq \mathbf{X} \leq 10000$. - $1 \leq \mathbf{L} \times \mathbf{X} \leq 10000$. **Large dataset(17 Pts)** - Time limit: ~~480~~ 10 seconds. - $1 \leq \mathbf{X} \leq 10^{12}$. - $1 \leq \mathbf{L} \times \mathbf{X} \leq 10^{16}$.