There are $n$ participants in a competition with ability values $a_1, \dots, a_n$. A higher ability value indicates a stronger participant. The rank of a participant is defined as $1 + (\text{number of participants with an ability value greater than theirs})$.

While ranking based on ability values seems fair, different participants excel in different fields. Therefore, depending on the type of problem, a participant's ability value changes. For example, if we set 6 counting problems, the ability value of a participant who knows nothing about counting can be considered 0. In this problem, the type of problem is represented by a non-negative integer $k$, and under this problem type, a participant's ability value changes from $x$ to $x \operatorname{xor} k$.

As the problem setter, you want to manipulate the competition. You have $Q$ queries, where the $i$-th query $(x_i, y_i)$ asks whether there exists an integer $k$ such that the rank of the $x_i$-th participant is exactly $y_i$ when the problem type is $k$.

Let $ans_i$ be the answer to the $i$-th query. If the answer is "yes", $ans_i = 1$; otherwise, $ans_i = 0$.

To reduce the output complexity, you only need to calculate $\sum_{i=1}^{Q} ans_i \cdot i^2$. Although this value is not very large, to make this problem look more like a counting problem, you must output the result modulo $998244353$.

Input

The first line contains two positive integers $n$ and $Q$.

The second line contains $n$ non-negative integers representing $a_1, \dots, a_n$.

The next $Q$ lines each contain two positive integers $x_i$ and $y_i$, representing the $i$-th query.

Output

Output a single non-negative integer representing the result modulo $998244353$.

Examples

Input 1

5 4
1 2 3 4 5
2 1
1 3
3 4
4 2

Output 1

30

Subtasks

Task 1 (7 pts): $a_i < 2^{12}$.

Task 2 (18 pts): $n \leq 1000$.

Task 3 (15 pts): $n \leq 5000$.

Task 4 (20 pts): $Q \leq 50000$.

Task 5 (40 pts): No additional restrictions.

For all data, $1 \leq n \leq 50000$, $0 \leq a_i < 2^{60}$, $1 \leq Q \leq 10^6$, and $1 \leq x_i, y_i \leq n$.