XOR Queries

Interview

Time limit2sMemory limit1024 MB

Summary

Given an array with point updates, find the i-th largest value after XOR-ing every element with x, for each type 2 query.

Problem

A sequence of integers $a=[a_1,a_2,\ldots,a_N]$ of length $N$ is given. Write a program that processes the following queries.

$1$ $i$ $x$ : Change the value of $a_i$ to $x$ .
$2$ $i$ $x$ : Print the $i$ -th largest value, counting duplicates, in the sequence $[a_1\oplus x,a_2\oplus x,\ldots,a_N\oplus x]$ .

Here, $a\oplus b$ is the bitwise exclusive OR (xor) of $a$ and $b$ .

The first line contains the length $N$ of the sequence $a$ . $(1\le N\le 100\,000)$

The second line contains $N$ integers $a_1,a_2,\ldots,a_N$ , separated by spaces. $(0\le a_i\le 2^{31}-1)$

The third line contains the number of queries $Q$ . $(1\le Q\le 100\,000)$

From the fourth line on, $Q$ lines follow, each containing one query. Type 2 queries appear at least once. $(1\le i\le N;\ 0\le x\le 2^{31}-1)$

For each type 2 query, print the result on its own line.

Example 1

Input

9
1 2 3 4 5 6 7 8 9
11
2 1 7
2 2 7
2 3 7
1 1 3
1 2 3
1 4 3
2 1 12
2 2 12
2 3 12
2 4 12
2 5 12

Expected output