J. Joining Xegos
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Tiago DFS is going to China!!

And, taking advantage of the trip, he decides to go to the largest ancestral store in the city to buy the pieces missing from his xego collection.

The xego section can be represented by an immense shelf with $$$N$$$ xegos available, in positions numbered from $$$1$$$ to $$$N$$$, for purchase.

But the eccentric Chinese owner of the store chooses a continuous interval $$$[L, R]$$$ every day and allows customers to buy only the items within that interval. Additionally, he only allows the customer to enter the store once a day, so always choose wisely which items you will buy before leaving the store.

After hours, the owner himself always restocks the items that were purchased that day with the same items.

Moreover, each xego piece has an identifier, which can be represented by a unique positive integer $$$a_i$$$.

And everyone knows that if we combine xegos, we can form other xegos, which can also, in turn, be combined into other xegos.

After playing a lot with xegos, Tiago noticed a curious property: the combination of two xegos $$$A$$$ and $$$B$$$ into another xego $$$C$$$ can be exactly described as the XOR operation of their identifiers. That is, $$$A \oplus B = C$$$.

Knowing that he will have $$$Q$$$ free days to buy xegos, help Tiago to answer, for each day, how many distinct combinations of shelf positions he can buy to form the xego $$$X$$$, knowing that on that day the owner allowed the sale only of the continuous interval $$$[L, R]$$$.

Input

The first line contains a positive integer $$$N$$$ ($$$1 \le N \leq 3 \cdot 10^5$$$) indicating the number of xegos on the shelf.

The second line contains $$$N$$$ positive integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^{18}$$$), representing the xegos arranged on the shelves.

The third line contains a positive integer $$$Q$$$ ($$$1 \le Q \leq 3 \cdot 10^5$$$) representing the number of days Tiago will go shopping.

Then, in the next $$$Q$$$ lines, three positive integers $$$L$$$, $$$R$$$ ($$$1 \leq L \leq R \leq N$$$), and $$$X$$$ ($$$1 \leq X_i \leq 10^{18}$$$) will be given, representing the limits of the interval and the xego of the day.

Output

For each day $$$Q$$$, respond with how many ways Tiago can form the xego $$$X$$$, knowing that only the continuous interval $$$[L, R]$$$ is available for purchase. Knowing that the value can be quite high, print the answer as the remainder of this value divided by $$$998 244 353$$$.

Examples
Input
5
1 2 4 8 16
3
1 3 7
1 5 19
4 4 16
Output
1
1
0
Input
4
2 1 1 2
3
1 3 3
1 4 2
1 4 4
Output
2
4
0
Note

Test Case 1:

For day 1, Tiago can choose all the xegos in the interval $$$[1, 3]$$$, obtaining $$$1 \oplus 2 \oplus 4 = 7$$$.

For day 2, Tiago can choose the xegos at positions #$$$1$$$, #$$$2$$$, and #$$$5$$$, obtaining $$$1 \oplus 2 \oplus 16 = 19$$$.

For day 3, Tiago can only choose the item at position #$$$4$$$, which is of type $$$8$$$, and cannot generate $$$16$$$.

Test Case 2:

For day 1, there are 2 valid combinations {#$$$1$$$, #$$$2$$$} and {#$$$1$$$, #$$$3$$$}.

For day 2, there are 4 valid combinations {#$$$1$$$}, {#$$$4$$$}, {#$$$1$$$, #$$$2$$$, #$$$3$$$} and {#$$$2$$$, #$$$3$$$, #$$$4$$$}.

For day 3, there are no valid combinations.