There are $n$ reagents in the laboratory, numbered $1, 2, \dots, n$, where the danger level of reagent $i$ is $i$. You are conducting chemical experiments, but currently, you do not know any chemical reactions. There are $q$ events, each of which is one of the following two types:

1 x y: You learn how to convert reagent $x$ and reagent $y$ into each other through a chemical reaction.

2 x y: You currently have reagent $x$. Find the number of reagents $x^\prime$ such that you can produce reagent $x^\prime$ from reagent $x$ through a series of reactions, and the danger level of all reagents involved in the process does not exceed $y$.

Since you are eager to know the experimental results, the queries are forced to be online.

Input

The first line contains three integers $t, n, q$.

The next $q$ lines each contain three integers $op, x_0, y_0$, representing an event op x y, where $x = (x_0 - 1 + t \times lastans) \bmod n + 1$, $y = (y_0 - 1 + t \times lastans) \bmod n + 1$, and $lastans$ is the answer to the previous query (or $0$ if there is no previous query).

Output

For each event where $op = 2$, output a single integer on a new line representing the answer.

Examples

Input 1

0 5 15
1 3 4
2 1 4
1 5 1
2 5 5
1 3 5
1 4 3
1 2 1
2 2 4
2 4 4
2 4 5
2 2 2
2 1 3
1 1 5
1 3 1
2 3 4

Output 1

1
2
2
2
5
2
2
4

Constraints

For all test cases, $t \in \{0, 1\}$, $1 \le n, q \le 5 \times 10^5$, $op \in \{1, 2\}$, $1 \le x_0, y_0 \le n$. When $op = 1$, $x \neq y$; when $op = 2$, $x \le y$.