2017 Ho Chi Minh City Regional Contest

Start

2017-12-07 16:15 AKST

2017 Ho Chi Minh City Regional Contest

End

2017-12-07 21:15 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -1227 days 19:06:55

5:00:00

0:00:00

Problem KK-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