2017 Ho Chi Minh City Regional Contest

Start

2017-12-08 02:15 CET

2017 Ho Chi Minh City Regional Contest

End

2017-12-08 07:15 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -250 days 8:12:00

Time elapsed

5:00:00

Time remaining

0:00:00

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