You are given an array of $A$ integers. You must perform $Q$ queries on this array.

The queries must be one of the following types:

1. $x$:  Add element $x$ to the start of the array.
2. $x$: Add element $x$ to the end of the array.
3. $x\ y$: Print the XOR elements from the indices ranging from $x$ to $y$.

The array is 1-indexed.

For every query of type $3$, print the answer to the query.

Input format

• First line: $q$
• Next $q$ lines: Queries of types $1$, $2$, or $3$ is provided

Output format

For every query of type $3$, print the answer to the query.

Constraints

$1 \le q \le 3 \times 10^5$

In the first and second type of queries, $0 \le x \le 10^9$

In the third type of queries, $1 \le x \le y \le n$, where $n$ is the current size of the array