No.2716 Falcon Method
Problem Statement
You are given a string $S = S_0 S_1 \cdots S_{N-1}$ of length $N$ consisting only of D and R (note that the indices start from $0$).
Define the procedure $F(h, w, p)$, which moves on a two-dimensional grid, as follows:
- Initialize the position to $(0, 0)$ and the counter value to $p$.
- When the current position is $(x, y)$ and the counter value is $i$:
- If $x = h$ and $y = w$, terminate the procedure.
- Otherwise, if $x = h$, update the position to $(x, y + 1)$ and return to 2.
- Otherwise, if $y = w$, update the position to $(x + 1, y)$ and return to 2.
- Otherwise, where $\bmod$ denotes the binary operator for the remainder:
- If $S_i=$
D, update the position to $(x + 1, y)$ and the counter to $(i + 1) \bmod N$, and return to 2. - If $S_i=$
R, update the position to $(x, y + 1)$ and the counter to $(i + 1) \bmod N$, and return to 2.
- If $S_i=$
You are given $Q$ queries. The $i$-th query is represented by a tuple of integers $(H_i, W_i, P_i)$. Find the counter value after the procedure $F(H_i, W_i, P_i)$ has finished.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq Q \leq 10^5$
- $1 \leq H_i, W_i \leq 10^9$
- $0 \leq P_i < N$
- $S$ is a string of length $N$ consisting only of
DandR - All numerical values in the input are integers
Input
The input is given from Standard Input in the following format.
$N \ Q$ $S$ $H_1 \ W_1 \ P_1$ $\vdots$ $H_Q \ W_Q \ P_Q$
Output
Output $Q$ lines. On the $i$-th line, output the counter value after the procedure $F(H_i, W_i, P_i)$ has finished.
Print a newline at the end.
Sample
Sample 1
Input
4 3 RDDR 3 2 1 1 7 0 4 1 3
Output
1 2 0
The $1$-st query is $(3, 2, 1)$, and the procedure $F(3, 2, 1)$ proceeds as follows:
- Initialize the position to $(0, 0)$ and the counter value to $1$.
- Since $0 < 3, 0 < 2$ and $S_1=$
D, update the position to $(0+1, 0)=(1, 0)$ and the counter value to $(1+1) \bmod 4 = 2$. - Since $1 < 3, 0 < 2$ and $S_2=$
D, update the position to $(1+1, 0)=(2, 0)$ and the counter value to $(2+1) \bmod 4 = 3$. - Since $2 < 3, 0 < 2$ and $S_3=$
R, update the position to $(2, 0+1)=(2, 1)$ and the counter value to $(3+1) \bmod 4 = 0$. - Since $2 < 3, 1 < 2$ and $S_0=$
R, update the position to $(2, 1+1)=(2, 2)$ and the counter value to $(0+1) \bmod 4 = 1$. - Since $2 < 3, 2 = 2$, update the position to $(2+1, 2)=(3, 2)$.
- Since $3 = 3, 2 = 2$, terminate the procedure.
The counter value after the procedure has finished is $1$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hamamu