G. Cosmic Travel
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

BaoBao is a cosmic traveler, shuttling between an infinite number of parallel universes. Each universe is numbered with an integer starting from $$$0$$$.

There are $$$n$$$ magic apples in each universe. Although these universes have many similarities, there are still slight differences between them. The magic power of the $$$i$$$-th apple in the $$$j$$$-th universe is $$$a_i\oplus j$$$. Here $$$\oplus$$$ denotes bitwise exclusive or operation.

BaoBao is very indecisive, so he prepared $$$q$$$ traveling plans. Each traveling plan can be described by three integers $$$l$$$, $$$r$$$ and $$$k$$$, which means BaoBao will travel to each universe numbered from $$$l$$$ to $$$r$$$ (both inclusive), and collect the apple with the $$$k$$$-th smallest magic power among the $$$n$$$ apples in each universe.

For each traveling plan, please help BaoBao calculate the sum of the magic power of the apples he collects. Note that the traveling plan does not really remove the apple from each universe. That is, each query is independent.

Input

There is only one test case in each test file.

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\leq n, q\leq 10^5$$$) indicating the number of apples in each universe and the number of plans.

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

For the following $$$q$$$ lines, the $$$i$$$-th line contains three integers $$$l_i$$$, $$$r_i$$$ and $$$k_i$$$ ($$$0\leq l_i\leq r_i \lt 2^{60}$$$, $$$1\leq k_i\leq n$$$) indicating the $$$i$$$-th traveling plan.

Output

For each traveling plan output one line containing one integer indicating the answer for that plan. As the answer might be large, output it modulo $$$998244353$$$.

Example
Input
8 3
2 0 2 4 0 5 2 6
1 1 6
2 7 5
0 1048575 4
Output
4
23
720895450