XOR Game

Time limit3sMemory limit512 MB

Summary

Given an array with point updates, answer range queries for the index whose XOR with x is smallest or largest, breaking ties by the smallest index.

Problem

Jaehyeon and Junhyeok's favorite game these days is the XOR game.

In the XOR game, given an array $A$ , the following queries are processed.

1 $l$ $r$ $x$ : Among all $i$ satisfying $l \le i \le r$ , choose the $A_i$ whose XOR with $x$ is the smallest, and print that $i$ . If several such $i$ exist, print the smallest one.
2 $l$ $r$ $x$ : Under the same conditions, choose the $A_i$ whose XOR with $x$ is the largest, and print that $i$ . If several such $i$ exist, print the smallest one.
3 $p$ $x$ : Change $A_p$ to $x$ .

Write a program that runs the XOR game for Jaehyeon and Junhyeok.

The first line contains the size $N$ of the initial array. $(1 \le N \le 100,000)$

The second line contains the $N$ elements $A_i$ of the initial array. $(0 \le A_i \le 10^7)$

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

Each of the next $Q$ lines contains a query. $(0 \le x \le 10^7$ , $1 \le l \le r \le N$ , $1 \le p \le N)$

For each query of type 1 or 2, print the answer on its own line, in the order the queries are given.

Example 1

Input

7
92 104 100 43 28 108 97
9
2 2 6 76
1 3 4 66
2 6 7 6
3 6 16
2 6 6 101
1 7 7 69
3 6 6
2 1 3 108
1 5 5 124

Expected output