問題文

正整数 $N, Q$ と、すべての要素が $0$ または $1$ からなる長さ $N$ の数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。

$A$ に対して、$i = 1, 2, \ldots, Q$ について、以下の操作を行います。

• $L_i, R_i$ が与えられるので、$A_{L_i}, A_{L_i+1}, \ldots, A_{R_i}$ をフリップする。

すべての操作を終えた後の $A$ を出力してください。

ただし、$x$ をフリップするとは、$x = 0$ なら $x = 1$ に、 $x = 1$ なら $x = 0$ にすることを指します。

なお、この制約において、$x \neq 0$ かつ $x \neq 1$であるような $x$ をフリップすることはありません。

入力

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

入力は全て以下の制約を満たす。

• $1 \leq N, Q \leq 5 \times 10^{5}$
• $A_i = 0$ もしくは $A_i = 1$
• $1 \leq L_i \leq R_i \leq N$
• 入力はすべて整数

出力

以下の形式で、操作を全て行った後の$A$を出力し、最後に改行してください。

$A_1\ A_2\ \ldots\ A_N$

サンプル

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