这是一个交互式问题。

给定一个包含 $n$ 个整数的数组 $a_1, \dots, a_n$。你需要处理两种类型的查询：

• “$1\ x\ y$”：将 $a_x$ 的值修改为 $y$。
• “$2\ l\ r$”：在区间 $a_l, a_{l+1}, \dots, a_r$ 中查找并输出一个出现次数为奇数的数字，或者确定不存在这样的数字并输出 $-1$。如果有多个符合条件的数字，你可以输出其中任意一个。

交互

你的程序必须从标准输入读取数据并向标准输出写入数据。

输入以两行开始：第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，第二行包含 $n$ 个空格分隔的整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$)。

随后是查询块描述。

每个查询块描述以一行包含查询数量 $q_i$ 开始。如果该数字为 $0$，则程序必须立即正常终止。否则，接下来会有 $q_i$ 行查询描述。

每个查询描述为 “$1\ x\ y$” ($1 \le x \le n, 1 \le y \le 10^5$) 或 “$2\ l\ r$” ($1 \le l \le r \le n$)。

对于每个类型为 2 的查询，请在单独的一行中打印答案。你必须在当前块中回答所有类型为 2 的查询（如果有的话），才能接收下一个块的数据。打印答案后，请务必刷新输出，例如在 C 或 C++ 中使用 fflush(stdout)，在 Java 中使用 System.out.flush()。否则，最可能的结果是 “Idleness Limit Exceeded”（空闲时间超限）。

所有块中的查询总数不超过 $10^5$。保证至少有一个类型为 2 的查询。

样例

输入 1

5
1 2 2 3 3
2
2 1 5
1 1 3
3
2 1 4
1 5 4
2 2 5
0

输出 1

1
-1
3