Introductory Problems: XOR Basis
A. Distinct Xor Subsequences
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ .

Count the distinct numbers you can produce by choosing any subsequence from $$$a$$$ and calculate their bitwise XOR. The chosen subsequence can be empty.

Input

The first line of input contains a single integer $$$n \ (1 \le n \le 10^5)$$$.

Then, the second line contains $$$n$$$ integers $$$a_1, \dots , a_n \ (0 \le a_i \lt 2^{60})$$$.

Output

Print a line of a single integer denoting the answer.

Examples
Input
4
7 2 1 5
Output
8
Input
7
1 1 1 1 1 1 1
Output
2

B. Distinct Xor Subsequence Queries
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an empty sequence $$$a$$$. Your task is to process $$$q$$$ queries of the following types:

1. Append $$$x$$$ to the end of sequence $$$a$$$;

2. Among all distinct numbers you can produce by choosing any subsequence(possibly empty) from $$$a$$$ and calculating their bitwise XOR, print the $$$k$$$-th smallest one. If such a number does not exist, print $$$-1$$$ instead.

Input

The first line of input contains a single integer $$$q \ (1 \le q \le 2 \times 10^5)$$$.

Then, there are $$$q$$$ lines describing the queries. Each line has two integers: $$$1\ x \ (0 \le x \lt 2^{60})$$$ or $$$2\ k \ (1 \le k \le 2^{60})$$$

Output

For each query of type 2, print a line of a single integer denoting the answer.

Examples
Input
7
1 5
1 6
2 1
2 2
2 3
2 4
2 5
Output
0
3
5
6
-1
Input
3
1 1000
1 1000
2 3
Output
-1

C. Distinct Xor Subsequence Queries Ⅱ
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an empty sequence $$$a$$$. Your task is to process $$$q$$$ queries of the following types:

1. Append $$$x$$$ to the end of sequence $$$a$$$;

2. Consider all $$$2^k$$$ possible subsequences of $$$a$$$, where $$$k$$$ represents the current length of $$$a$$$. Among these subsequences, determine how many have a bitwise XOR value equal to $$$x$$$. Output the result modulo $$$998244353$$$.

Input

The first line of input contains a single integer $$$q \ (1 \le q \le 2 \times 10^5)$$$.

Then, there are $$$q$$$ lines describing the queries. Each line has two integers: $$$1\ x \ (0 \le x \lt 2^{60})$$$ or $$$2\ x \ (0 \le x \lt 2^{60})$$$

Output

For each query of type 2, print a line of a single integer denoting the answer.

Examples
Input
6
1 5
1 6
2 0
2 1
2 2
2 3
Output
1
0
0
1
Input
10
1 2024
1 2024
1 2024
1 2024
2 2024
1 1
1 1
1 1
1 1
2 2025
Output
8
64

D. Range Xor Subsequence Query
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence of $$$n$$$ integers $$$a_1, \dots , a_n$$$. Your task is to process the $$$q$$$ queries of the following:

- Given $$$l, r, x$$$, check if it's possible to choose several integers from $$$a_l, a_{l+1}, \dots , a_r$$$ such that their bitwise XOR is $$$x$$$. Print "Yes" if possible, print "No" otherwise.

Input

The first line of input contains a single integer $$$n \ (1 \le n \le 10^5)$$$.

The second line contains $$$n$$$ integers $$$a_1, \dots, a_n \ (0 \le a_i \lt 2^{60})$$$ denoting the sequence.

Then the next line contains a single integer $$$q \ (1 \le q \le 5 \times 10^5)$$$.

Then, for the following $$$q$$$ lines, each line contains $$$3$$$ integers $$$l, r, x \ (1 \le l \le r \le n, 0 \le x \lt 2^{60})$$$ denoting a query.

Output

For each query, print a single line of 'Yes' or 'No'.

Example
Input
5
2 4 1 16 8
4
1 3 20
2 4 20
1 5 31
1 5 32
Output
No
Yes
Yes
No

E. Constructive Xor
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ .

Your task is to answer $$$q$$$ queries:

- Choose several numbers from $$$a_1, a_2, \dots , a_n$$$ such that their bitwise XOR is $$$x$$$. If their are multiple solutions, print any of them.

It's guaranteed that at least one solution exists for each query.

Input

The first line of input contains a single integer $$$n \ (1 \le n \le 500)$$$.

The second line contains $$$n$$$ integers $$$a_1, \dots, a_n \ (0 \le a_i \lt 2^{60})$$$.

Then, the third line contains a single integer $$$q \ (1 \le q \le 1000)$$$.

For the next $$$q$$$ lines, each line contains a single integer $$$x \ (0 \le x \lt 2^{60})$$$ denoting a query.

Output

For each query, print a line of $$$n$$$ zeros and/or ones. The $$$i$$$-th character should be '1' if the solution contains $$$a_i$$$, or should be '0' otherwise.

Example
Input
6
2 15 12 0 5 4
5
10
8
3
6
7
Output
010010
110010
011000
011010
100010