H. Traffic Lights
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

A street has $$$N$$$ traffic lights, numbered from $$$1$$$ to $$$N$$$. Each traffic light can be in one of two states: closed, represented by $$$1$$$, or open, represented by $$$0$$$.

To prepare the street for a special operation, $$$M$$$ control devices have been installed. Each device acts on a contiguous stretch of the street: when activated, it toggles the state of every traffic light within its range. Thus, closed traffic lights are opened, and open traffic lights are closed.

The $$$i$$$-th device affects the traffic lights whose indices are between $$$L_i$$$ and $$$R_i$$$, inclusive. Each device can be activated as many times as needed.

Is it possible to activate the devices so that all traffic lights end up open?

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 10^{5}$$$), representing, respectively, the number of traffic lights and the number of control devices.

The second line contains $$$N$$$ integers $$$v_1, v_2, \dots, v_N$$$ ($$$v_i \in \{0, 1\}$$$), representing the initial state of the traffic lights.

Each of the following $$$M$$$ lines describes a device. The $$$i$$$-th of these lines contains two integers $$$L_i$$$ and $$$R_i$$$ ($$$1 \leq L_i \leq R_i \leq N$$$), indicating that device $$$i$$$ affects all traffic lights between $$$L_i$$$ and $$$R_i$$$, inclusive.

Output

Print YES if it is possible to leave all traffic lights open, or NO otherwise.

Example
Input
5 4
0 1 1 0 1
3 5
3 3
1 3
2 4
Output
YES