Ed has N bulbs, arranged in a line, with him. A[i] denotes the initial state of 'i'th Bulb. He wants to toggle some bulbs, but he can only toggle the bulbs in ranges. Toggling a bulb means changing the state of the bulb. That is, if the bulb was ON then after toggling it becomes OFF. He does this 'range toggling' Q times. In the 'i'th range toggling, he toggles the bulbs all the bulbs between Li and Ri bulbs (Li and Ri inclusive). You need to find the final states of all the N bulbs after these Q toggles.

A[i] = 1 means the Bulb is ON and A[i] = 0 means the Bulb is OFF

INPUT:

First line contains N and Q. The next line contains N integers showing the initial state of the bulbs. The next Q line contains the queries where 'i'th line contains Li and Ri.

OUTPUT:

In a single line, output N integers showing the final state of the bulbs.

CONSTRAINTS:

1<=N<=10^5

1<=Q<=10^5

1<=Li<=Ri<=N

0<=A[i]<=1