书架藏书

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有 \(n\) 个书架。每个书架位置数量不一，第 \(i\) 个书架有 \(p_i (p_i≤10^5)\) 个位置，每个书架的位置编号从 1 开始，一直到 \(a_i\)。现在有 \(m(m≤10^6)\) 次操作：

　　\(1\ x\ y\ k\)：在第 \(x\) 个书架的第 \(y\) 个位置存入书本 \(k(0≤k≤10^9)\)。当 \(k=0\) 时说明该位置书被取走。
　　\(2\ x\ y\)：查询第 \(x\) 个书架的第 \(y\) 个位置中的书本是什么，有可能查询的书架没有存过书本，此时输出 0。

【输入格式】

　　第一行 2 个整数 \(n\) 和 \(m\)，书架个数和询问次数。
　　接下来 \(m\) 个整数，表示一次操作。

【输出格式】

　　对于查询操作时，输出答案。

【输入输出样例】

　Input

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

　Output

118014
1

【数据限制】

　　对于 \(100\%\) 的数据，有 \(n,m≤100000\)，且总共的位置个数不超过 \(10^7\)。

【来源】

　　Mr.he