序列维护

题目描述

你要维护$n$个序列$p_1, p_2, \dots, p_n$，一开始都是空的。接下来需要支持$q$个操作：

1. 1 x y，往序列$p_x$末尾插入一个数$y$，每个序列的下标都是从$0$开始的。
2. 2 z，对于所有非空的序列$p_i$，求出$p_{i, z \bmod |p_i|}$的和，其中$|p_i|$表示序列$p_i$中数字个数。

输入格式

第一行两个整数$n, q (1\leq n\leq 2\times 10^5, 1\leq q\leq 4\times 10^5)$。

接下来$q$行，每行一个操作，保证$1\leq x\leq n, 1\leq y, z\leq 10^9$。

输出格式

对于每个查询操作，输出一个数，表示答案。

样例输入

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

样例输出

0
1
2
1
2