시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
12 초 512 MB 2 2 2 100.000%

문제

This is an interactive problem.

You are given an array $a_1, \ldots, a_n$ of $n$ integers. You have to process queries of two types:

  • "1 $x$ $y$": change value of $a_x$ to $y$.
  • "2 $l$ $r$": find and print a number that occurs an odd number of times in the segment $a_l, a_{l + 1}, \ldots, a_r$, or determine that there is no such number and print $-1$ instead. If there are several suitable numbers, you can output any of them.

프로토콜

Your program must read from standard input and write to standard output.

The input starts with two lines: the first line contains an integer $n$ ($1 \le n \le 10^5$), and the second line contains $n$ space-separated integers $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \le a_i \le 10^5$).

Then follow query block descriptions.

Each query block description starts with a line containing the number of queries $q_i$. If this number is $0$, the solution must immediately terminate gracefully. Otherwise, $q_i$ query descriptions follow, one per line.

Each query description is either "1 $x$ $y$}" ($1 \le x \le n$, $1 \le y \le 10^5$) or "2 $l$ $r$" ($1 \le l \le r \le n$).

For each query of type 2, print the answer on a separate line. You must answer all queries of type 2 in the current block, if there are any, to receive the next block.

The total number of queries in all blocks does not exceed $10^5$. It is guaranteed that there is at least one query of type 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

채점

  • 예제는 채점하지 않는다.