为了确保保密性,“俄罗斯代码杯”问题的访问在问题开发过程中受到密码保护。
为了选择密码,陪审团可以生成一个包含 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