[Contest #15]栈的数据结构题

内存限制：256 MB 时间限制：2000 ms

初始时有 $N$ 个空的栈，编号为 $1 \sim N$，有以下三种类型的指令：

push $L$ $R$ $v$：把编号 $L \sim R$ 这连续 $R-L+1$ 个栈都 push 一个数 $v$。
pop $L$ $R$：把编号 $L \sim R$ 这连续 $R-L+1$ 个栈都执行 pop 一次，保证进行此指令时，这 $R-L+1$ 个栈都不为空。
find $id$ $pos$：询问第 $id$ 个栈由栈顶数来第 $pos$ 个数字是什么，保证进行此指令时，第 $id$ 个栈至少有 $pos$ 个数字。

输入会给你总共 $Q$ 个指令，对于每个 find 指令请输出正确答案。

第一行有两个正整数 $N$ 和 $Q$，分别代表栈的数目及指令的数目。

接下来有 $Q$ 行，每行的格式即题目描述里三种指令之一，也就是 push $L$ $R$ $v$、pop $L$ $R$ 或 find $id$ $pos$。

$1 \le N, Q \le 2 \times 10^5$
$1 \le L \le R \le N$
$1 \le v \le Q$
$1 \le id \le N$
保证每次执行 pop 指令时，编号 $L \sim R$ 这 $R-L+1$ 个栈都非空
保证每次执行 find 指令时，编号 $id$ 的栈至少包含 $pos$ 个
输入中的所有数都是正整数

对于每个 find 指令输出一行包含一个正整数，代表当前第 $id$ 个栈由栈顶数来第 $pos$ 个数字是什么。

样例输入 1

3 9
push 1 3 1
push 1 2 2
find 2 2
find 2 1
push 2 3 3
find 3 1
find 3 2
pop 1 3
find 3 1

样例输出 1