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