I. Bessie and XOR
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bessie has an array $$$a$$$ of length $$$n$$$ and a list of $$$m$$$ intervals $$$[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$$$.

In one operation, Bessie can choose one of the $$$m$$$ given intervals $$$[l_i, r_i]$$$ and a non-negative integer $$$x$$$, and XOR all elements $$$a_{l_i}, a_{l_i+1}, \ldots, a_{r_i}$$$ with $$$x$$$.

She may use each interval any number of times (possibly zero), with possibly different values of $$$x$$$ each time. Determine whether it is possible to make all elements of $$$a$$$ equal to zero using at most $$$m$$$ operations. If it is possible, construct such a sequence of operations. Note that Bessie doesn't need to minimize the number of operations.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le m \le 200\,000$$$) — the length of the array and the number of intervals.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$) — the elements of the array.

Each of the next $$$m$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the endpoints of the $$$i$$$-th interval.

Output

If it is impossible, print $$$-1$$$.

Otherwise, print an integer $$$k$$$ ($$$0 \le k \le m$$$) — the number of operations. Then print $$$k$$$ lines. The $$$j$$$-th of these lines should contain two integers $$$i_j$$$ and $$$x_j$$$ ($$$1 \le i_j \le m$$$, $$$0 \le x_j \le 10^9$$$) — meaning that in the $$$j$$$-th operation, the interval $$$[l_{i_j}, r_{i_j}]$$$ is XORed with $$$x_j$$$.

If there are multiple valid solutions, print any of them.

Examples
Input
3 3
3 1 2
1 3
2 3
1 2
Output
2
2 2
3 3
Input
3 2
1 2 3
1 1
3 3
Output
-1
Note

In the first example, one valid solution uses $$$2$$$ operations:

  1. Use interval $$$2$$$ ($$$[2, 3]$$$) with $$$x = 2$$$: $$$[3, 1 \oplus 2, 2 \oplus 2] = [3, 3, 0]$$$.
  2. Use interval $$$3$$$ ($$$[1, 2]$$$) with $$$x = 3$$$: $$$[3 \oplus 3, 3 \oplus 3, 0] = [0, 0, 0]$$$.

In the second example, it is impossible to make all elements zero.