Given a sequence $a$ of length $n$.

We define an operation as simultaneously replacing each element $a_i$ in the sequence $a$ with $\bigoplus\limits_{j=1}^i a_j$ (the XOR sum of $a_1$ through $a_i$), where $\bigoplus$ denotes the bitwise XOR operation, i.e., ^ in C++.

There are $q$ sequential modifications. Each modification provides two integers $x_i$ and $p_i$, meaning the value of $a_{x_i}$ is updated to $p_i$. These modifications are not independent; each modification affects subsequent ones.

After each modification, you need to find the minimum positive integer $t$ such that the sequence $a$ after $t$ operations is identical to the sequence $a$ before any operations. It can be proven that such a positive integer $t$ always exists.

Since the answer can be very large, you only need to output the answer modulo $(10^9+7)$.

Input

The first line contains two integers $n$ and $q$.

The second line contains $n$ integers, representing the given sequence $a$.

The next $q$ lines each contain two integers $x_i$ and $p_i$, representing a modification.

Output

Output $q$ lines, each containing one integer. The $i$-th line represents the minimum positive integer $t$ satisfying the condition after the $i$-th modification, modulo $(10^9+7)$.

Examples

Input 1

3 3
3 1 0
2 2
1 0
2 0

Output 1

4
2
1

Note 1

After the first modification, the sequence $a$ is $\{3, 2, 0\}$. After $1$ operation, the sequence $a$ becomes $\{3, 1, 1\}$. After $2$ operations, the sequence $a$ becomes $\{3, 2, 3\}$. After $3$ operations, the sequence $a$ becomes $\{3, 1, 2\}$. After $4$ operations, the sequence $a$ becomes $\{3, 2, 0\}$. Therefore, the minimum positive integer $t$ is $4$.

Constraints

For all data, $1 \le n, q \le 3\times10^5$, $0 \le a_i, p_i \le 10^9$, $1 \le x_i \le n$.