Problem K
K-Rotating
A new school year has started. The high school for gifted students of Ho Chi Minh city has $N$ classes numbered from $1$ to $N$. All $N$ classes will go through $M$ studying weeks. The high school has $N$ teachers numbered from $1$ to $N$. At the beginning teacher $i$ is assigned to class $i$.
In order to improve the students adaptability to new knowledge or new teaching methods, the principal has plans to reassign the teachers every few weeks. A reassignment only happens at the beginning of a week (on Monday before classes start) and a week has at most $1$ reassignment. A reassignment is to rotate $K$ teachers $p_1, p_2, p_3, \ldots , p_ K$, described as follows:
-
Teacher $p_ i$ moves to the current class where teacher $p_{i+1}$ is teaching ($1 \leq i < K$).
-
Teacher $p_ K$ moves to the current class where teacher $p_1$ is teaching.
After the reassignment, the teachers will stay at the newly assigned classrom, until he is reassigned again.
The principal continuously add shuffle plans and he also asks questions: “When all the previous reassignment plans comes to effect, which class will teacher $d$ teach on Tuesday of the $x$-th week?” Your task is to help him answer all those questions.
Input
The first line contains $3$ integers: $N$, $M$ and $Q$ - the number of queries ($1 \leq N,M,Q \leq 10^5$). The next $Q$ lines describes $Q$ queries, each will be in either of the $2$ forms:
-
$0$ $K$ $x$ $p_1$ $p_2$ …$p_ K$ - add a plan to rotate $K$ teachers $p_1, p_2, \ldots p_ K$ on Monday of the $x$-th week ($1 \leq x \leq M$, $2 \leq K \leq 10$, all $K$ values in $p$ are unique).
-
$1$ $d$ $x$ - ask which class is taught by teacher $d$ on Tuesday of the $x$-th week.
It is guaranteed that there are no two queries of type $0$ has the same value $x$.
Output
For each of the queries type $1$, print the answer in a single line.
Clarification for the second sample
Initial assignment:
|
Class $1$ |
Class $2$ |
Class $3$ |
|
|
Week $1$ |
$1$ |
$2$ |
$3$ |
|
Week $2$ |
$1$ |
$2$ |
$3$ |
|
Week $3$ |
$1$ |
$2$ |
$3$ |
|
Week $4$ |
$1$ |
$2$ |
$3$ |
After rotate $(3, 2)$ on Monday of the $2^\textrm {nd}$ week:
|
Class $1$ |
Class $2$ |
Class $3$ |
|
|
Week $1$ |
$1$ |
$2$ |
$3$ |
|
Week $2$ |
$1$ |
$3$ |
$2$ |
|
Week $3$ |
$1$ |
$3$ |
$2$ |
|
Week $4$ |
$1$ |
$3$ |
$2$ |
After rotate $(3,1,2)$ on Monday of the $3^\textrm {rd}$ week:
|
Class $1$ |
Class $2$ |
Class $3$ |
|
|
Week $1$ |
$1$ |
$2$ |
$3$ |
|
Week $2$ |
$1$ |
$3$ |
$2$ |
|
Week $3$ |
$3$ |
$2$ |
$1$ |
|
Week $4$ |
$3$ |
$2$ |
$1$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 5 1 3 4 0 2 2 3 2 1 3 2 1 2 4 1 1 4 |
3 2 3 1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 4 6 1 3 4 0 2 2 3 2 1 3 2 0 3 3 3 1 2 1 2 4 1 1 4 |
3 2 2 3 |
