C. 天才琪露诺与克劳恩皮丝
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output
大胜、常胜、秦河胜！
妖精大战争 ～ Fairy Wars

克劳恩皮丝是地狱的妖精，有提高妖精生命力的能力。

太阳花田里的 n 只妖精排成一列。每个妖精都有一个生命力，初始时生命力均为 0。

克劳恩皮丝会施展能力提高妖精的生命力。具体而言，她会进行 m 次操作，分为两种：

  • 1 x w：从第 x 只妖精开始，将第 x 只妖精的生命力提高 w；接着往后数 g1 只妖精，将第 x + g1 只妖精的生命力提高 w；接着再往后数 g2 只妖精，将第 x + g1 + g2 只妖精的生命力提高 w......
  • 2 x：查询当前第 x 只妖精的生命力。

其中，g 是一个无穷长的序列，按照如下方式定义：

g 序列的前若干项如下：[1, 2, 1, 4, 1, 2, 1, 8, 1, 2, ...]。

为了防止你用某种方式作弊，操作都进行了加密。具体见输入格式。

Input

第一行有两个整数 n, m（1 ≤ n, m ≤ 3 × 105），分别表示妖精序列的长度以及操作的总次数。

接下来 m 行，描述每一次操作。

  • 1 x' w'：第一种操作，真实的 ，真实的 ；
  • 2 x'：第二种操作，真实的 。

其中 表示上一次查询的结果。特别地，一开始 。

数据保证解密后 1 ≤ x ≤ n，1 ≤ w ≤ 109。

Output

共若干行，对于每一条操作二，输出结果。

Example
Input
10 5
1 1 1
2 10
1 4 3
1 5 4
2 9
Output
1
7
Note

解密后的输入数据如下：

10 5
1 1 1
2 10
1 5 2
1 4 5
2 8
  • 初始时，序列内容为 0, 0, 0, 0, 0, 0, 0, 0, 0, 0；
  • 第 1 次操作后，序列内容为 1, 1, 0, 1, 1, 0, 0, 0, 1, 1；
  • 第 2 次操作查询 10 位置的元素，值为 1；
  • 第 3 次操作后，序列内容为 1, 1, 0, 1, 3, 2, 0, 2, 3, 1；
  • 第 4 次操作后，序列内容为 1, 1, 0, 6, 8, 2, 5, 7, 3, 1；
  • 第 5 次操作查询 8 位置的元素，值为 7.