P16368 [OOI 2026] March of the Sheep

Sasha is tired of the heavy city life and decided to move to the countryside. To occupy his time, he decided to raise sheep. For this purpose, he acquired a rectangular field in the village, which can be represented as a grid of size $n \times m$, where the rows are numbered from top to bottom with numbers from $1$ to $n$, and the columns are numbered from left to right with numbers from $1$ to $m$. On his field, Sasha bought $n$ sheep, each of which he assigned a whole row. Initially, the $i$-th sheep was placed in the cell with coordinates $(i, a_i)$ (in row number $i$ and column number $a_i$). Sasha found out that the sheep move only horizontally according to the following rules: - If there is exactly one column in the field, the sheep do not move. - Initially, the $i$-th sheep is in cell $(i, a_i)$, and each sheep has an initial direction in which it moves --- either left or right. There is no sheep that is in the first column and moves left, nor is there any sheep that is in the last column and moves right. - Every second, each sheep moves one column to the left if it is moving left; otherwise, it moves one column to the right. - If after moving a sheep ends up in column $1$ and is moving left, or if a sheep ends up in the last column and is moving right, it changes its direction to the opposite. Thus, the sheep never leave the boundaries of the field. :::align{center}  Here is an example of the sheep's movement, where initially the first sheep was in column $1$ and moved to the right, and the second was in column $3$ and moved to the left. The first picture shows the state at the beginning, the second after one second, the third after $2$ seconds from the start of movement, and the fourth after $3$ seconds from the start of movement. ::: Sasha does not like that the sheep move so chaotically; he wants all the sheep to move uniformly. This means that all sheep should be in the same column and have the same direction of movement. To achieve this, Sasha can trim his field several (possibly zero) times as follows: - He chooses a time $t$ (how many seconds have passed since the initial start of the sheep's movement) and the number of columns $x$ that will remain in the field after trimming. - All sheep at time $t$ must strictly lie within the field of size $n \times x$. This means that for any $i$ from $1$ to $n$, the $i$-th sheep at time $t$ must be in cell $(i, y_i)$, where $1 \leq y_i \leq x$. Otherwise, such a trimming of the field is not allowed. - After this operation, starting from time $t$, the number of columns on the field decreases to $x$. - Each sheep that is in the last column and moves to the right changes its direction to the opposite. Detailed examples of the trimming process are described in the notes section. Sasha wants to know if it is possible to achieve that all sheep move uniformly by trimming the field several times. If this is possible, Sasha wants to know what the maximum number of columns that can remain on the field is and how exactly he can achieve this. Help Sasha solve this problem!

The first line contains one integer $T$ ($1 \leq T \leq 3$) --- a parameter indicating what information about the answer needs to be output. A detailed description is provided in the "Output format". The second line contains two integers $n$ and $m$ ($2 \leq n \leq 200,000$, $2 \leq m \leq 10^9$) --- the number of rows and columns of the field. The third line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq m$) --- the column numbers where the sheep are initially located. The fourth line contains a string $s$ of length $n$, consisting only of the characters $\mathtt{L}$, $\mathtt{R}$, where the $i$-th character is $\mathtt{L}$ if the $i$-th sheep is initially moving left, and $\mathtt{R}$ if the $i$-th sheep is initially moving right. It is guaranteed that no sheep in the first column is moving left, and no sheep in the $m$-th column is moving right.

In the first line, output "No" (without quotes) if Sasha cannot achieve that all sheep move uniformly. Otherwise, output "Yes" (without quotes). If $T = 2$ or $T = 3$, then in the second line output the maximum number of columns that Sasha can leave on the field so that all sheep move uniformly. If $T=1$, then $\textbf{this should not be output}$. If $T = 3$, in the third line output the number $q$ ($0 \leq q \leq 10^6$) --- how many times Sasha will need to trim the field. In the next $q$ lines, output the description of the trimmings. For the description of each trimming of the field, output in one line two integers $t$ and $x$ ($0 \leq t \leq 10^{18}$, $1 \leq x < m$), where $t$ is the time at which Sasha needs to trim the field (from the very beginning of the sheep's movement), and $x$ is the number of columns that will remain on the field after this operation. The operations must be output in non-decreasing order of $t$. In each subsequent trimming, $x$ must be less than in the previous one. If there are multiple suitable sequences of trimmings, any of them can be output. It can be shown that under the given constraints, if a solution exists, then there exists a solution that fits within the given limits. In case $T = 1$ or $T = 2$, do not output the description of the trimmings.

### Note Consider the third example: The states of the sheep at zero seconds. :::align{center}  ::: The state of the sheep at one second. :::align{center}  ::: Trimmed the field to $4$ cells. :::align{center}  ::: The state of the sheep at two seconds. :::align{center}  ::: ### Scoring The tests for this problem consist of ten groups. Points for each group are awarded only if all tests of the group and all tests of some of the previous groups are passed. Note that passing the tests from the statement is not required for some groups. $\textbf{Offline testing}$ means that the results of testing your solution on this group will become available only after the end of the competition. The final score for each group equals the maximum score obtained for that group of tests across all submissions. | Group | Points | Additional constraints | < | < | Necessary groups | Comment | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | $T$ | $n$ | $m$ | | | | $0$ | $0$ | $--$ | $--$ | $--$ | $--$ | Tests from the statement. | | $1$ | $8$ | $T \leq 1$ | $--$ | $--$ | $--$ | | | $2$ | $11$ | $T \leq 2$ | $n \leq 3$ | $m \leq 4$ | $--$ | | | $3$ | $9$ | $--$ | $n = 2$ | $--$ | $--$ | $a_1 = 1, a_2 = m$ | | $4$ | $12$ | $--$ | $n = 2$ | $m \leq 200,000$ | $--$ | | | $5$ | $8$ | $--$ | $n = 2$ | $--$ | $3, 4$ | | | $6$ | $14$ | $T \leq 2$ | $n \leq 1000$ | $m \leq 1000$ | $2$ | | | $7$ | $10$ | $T \leq 2$ | $--$ | $--$ | $1, 2, 6$ | | | $8$ | $9$ | $--$ | $--$ | | $--$ | The string $s$ contains only the character $\mathtt{R}$. | | $9$ | $12$ | $--$ | $n \leq 1000$ | $m \leq 1000$ | $0, 2, 6$ | | | $10$ | $7$ | $--$ | $--$ | $--$ | $0$--$9$ | **Offline testing.** |