← 返回题目列表

Codeforces · 418/E

E. 棘手的密码

中文机器翻译题面 查看原题

为了确保保密性,“俄罗斯代码杯”问题的访问在问题开发过程中受到密码保护。

为了选择密码,陪审团可以生成一个包含 n 列和无限行数的特殊表。构建表格时,第一行是固定的,其他行通过以下规则获得:

在第 i 行的位置 p 处,有一个数字等于 a[i - 1][p] 出现在前缀 a[i - 1][1...p] 上的次数。

为了确保所需的保密级别,陪审团必须能够执行以下操作:

- 用 v 替换数字 a[1][p] 并重建表。
- 找到数字a[x][y],这将是新密码。

手动完成所有这些步骤非常乏味,因此陪审团请您帮助他。编写一个程序来响应陪审团的要求。

输入

第一行包含一个整数 n (1 ≤ n ≤ 100000) — 列数。第二行包含表格第一行的描述,即n个整数,不小于1且不超过109。

输入的第三行包含一个整数 m (1 ≤ m ≤ 100000) — 请求数。

接下来,每行包含请求的描述,该描述由三个整数组成:

- 如果第一个数字等于 1,则其余两个数字为 v、p (1 ≤ v ≤ 109;1 ≤ p ≤ n)。因此,您应该将值 v 放在第一行的位置 p 中。
- 如果第一个数字等于 2,则其余两个数字为 x、y (1 ≤ x ≤ 105; 1 ≤ y ≤ n) — 要从中获取值的表格单元格的行和列。

输出

按照您收到的顺序打印每个第二类型请求的答案。

示例

输入 #1

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

输出 #1

2
1