题目描述

仓库中有 $n(1\le n\le10^5)$ 个储物柜。每个储物柜的格子数量不同，第 $i$ 个储物柜有 $a_i(0\le a_i\le10^5)$ 个格子，但 $a_i$ 的具体数值未知。格子编号从 $1$ 开始。现在有 $q(1\le q\le10^5)$ 次操作：

• 1 i j k：将第 $i$ 个储物柜的第 $j$ 个格子存入物品 $k(0\le k\le10^9)$。当 $k=0$ 时表示清空该格子。
• 2 i j：查询第 $i$ 个储物柜的第 $j$ 个格子中的物品，保证该储物柜此前有过存入操作。

已知所有储物柜的格子总数不超过 $10^7$，$a_i$ 是确定的但未知，保证不小于该储物柜被请求的格子编号的最大值。某些储物柜可能没有任何格子。

输入格式

第一行两个整数 $n$ 和 $q$，分别表示储物柜个数和操作次数。

接下来 $q$ 行，每行若干个整数，描述一次操作。

输出格式

对于每次查询操作，输出对应格子中的物品编号，每行一个。

样例

5 4
1 3 10000 118014
1 1 1 1
2 3 10000
2 1 1

118014
1