题目描述

（本题的数据范围有所变化。）

梦云是一条鱼所以他有鱼的记忆，他需要你帮他记住所有披萨的重要程度。 给出 $q$ 次询问，有两种格式： 格式一：

1 x y

代表第$x$块披萨的重要程度是$y$。

格式二：

2 x

代表询问第$x$块披萨的重要程度。

输入格式

第一行输入一个整数 $q(1 \leq q \leq 2 \cdot 10^5)$，代表询问次数。

接下来输入 $q$ 次询问，格式同题面描述。$(1 \leq x, y \leq 10^9)$。

输出格式

对于每次格式2，输出一行整数表示答案。 特别地，如果询问的披萨梦云并没有记忆过，输出 $0$。

样例

4
1 1 3
2 1
1 4 5
2 4

3
5