Problem Statement

You are given positive integers $N, Q$ and a sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$ whose elements are all $0$ or $1$.

For $i = 1, 2, \ldots, Q$, perform the following operation on $A$.

• You are given $L_i, R_i$. Flip $A_{L_i}, A_{L_i+1}, \ldots, A_{R_i}$.

Output $A$ after all the operations are finished.

Here, to flip $x$ means to make it $x = 1$ if $x = 0$, and to make it $x = 0$ if $x = 1$.

Under these constraints, no $x$ with $x \neq 0$ and $x \neq 1$ is ever flipped.

Input

$N\ Q$
$A_1\ A_2\ \ldots\ A_N$
$L_1\ R_1$
$L_2\ R_2$
$\vdots$
$L_Q\ R_Q$

All input satisfies the following constraints.

• $1 \leq N, Q \leq 5 \times 10^{5}$
• $A_i = 0$ or $A_i = 1$
• $1 \leq L_i \leq R_i \leq N$
• All input values are integers.

Output

Output $A$ after performing all the operations in the following format, followed by a newline at the end.

$A_1\ A_2\ \ldots\ A_N$

Sample

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

1 0 1 0 1

10 7
1 0 1 1 1 1 0 0 1 1
3 6
1 10
4 4
1 7
3 3
2 10
8 8

1 1 0 0 1 1 1 1 1 1

30 24
1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 0 0 0 1 1 1
30 30
13 25
30 30
14 24
2 16
10 28
22 24
15 24
9 29
6 26
24 29
2 15
27 28
3 21
17 20
16 16
15 22
27 28
17 28
14 28
25 28
13 22
15 22
15 27

1 0 0 0 0 1 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0 1 1 1 1