一场比赛不能没有数据结构题，即使它只是一个气球题。

给你一个矩阵 $M$。设矩阵第 $i$ 行第 $j$ 列的元素为 $M_{i,j}$，行数和列数分别为 $n$ 和 $m$。初始时，$n = m = 1$，且 $M_{1,1} = c$。

你需要执行 $q$ 次操作，每次操作属于以下三种类型之一：

• 1 x y ($0 \le x \le n, 1 \le y \le 10^9$)：在第 $x$ 行和第 $(x + 1)$ 行之间插入一行，该行所有元素的值均为 $y$；此操作后，$n$ 增加 $1$；
• 2 x y ($0 \le x \le m, 1 \le y \le 10^9$)：在第 $x$ 列和第 $(x + 1)$ 列之间插入一列，该列所有元素的值均为 $y$；此操作后，$m$ 增加 $1$；
• 3 x y ($1 \le x \le n, 1 \le y \le m$)：查询 $M_{x,y}$ 的值。

输入格式

输入的第一行包含两个整数 $q, c$ ($1 \le q \le 5 \cdot 10^5, 1 \le c \le 10^9$)。

接下来的 $q$ 行，每行描述一个操作。

每行开头的三个整数 $opt, x, y$ ($opt \in \{1, 2, 3\}$) 的含义如上文所述。

输出格式

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

样例

输入样例 1

6 1
1 0 2
3 2 1
2 1 3
1 1 4
3 2 2
3 3 2

输出样例 1

1
4
3