Sequence Maintenance

Problem Description

You are to maintain $n$ sequences $p_1, p_2, \dots, p_n$, which are initially all empty. Then you must support $q$ operations:

1. 1 x y: append the number $y$ to the end of sequence $p_x$. The indices of every sequence start from $0$.
2. 2 z: for every non-empty sequence $p_i$, compute the element $p_{i,\, z \bmod |p_i|}$, and output the sum of all such elements, where $|p_i|$ denotes the number of elements in sequence $p_i$.

Input Format

The first line contains two integers $n, q$ ($1 \leq n \leq 2 \times 10^5,\ 1 \leq q \leq 4 \times 10^5$).

The next $q$ lines each describe one operation. It is guaranteed that $1 \leq x \leq n,\ 1 \leq y, z \leq 10^9$.

Output Format

For each query operation, output one number: the answer.

Sample Input

3 9
2 123
1 1 1
2 123
1 1 2
2 123
1 1 3
2 123
1 2 1
2 123

Sample Output

0
1
2
1
2

Constraints

• $1 \leq n \leq 2 \times 10^5$
• $1 \leq q \leq 4 \times 10^5$
• $1 \leq x \leq n,\ 1 \leq y, z \leq 10^9$ for every operation