403054: GYM100985 E MaratonIME rides the university bus

E. MaratonIME rides the university bustime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputIf we organize it correctly, ...Unknown

To make the trip to the subway less boring and tiring, the SPSU, Sao Paulo State University, tried one of its most famous inventions: buses with Infinite Inner Length! In such a modern engineering wonder, there's always a couple of empty seats for the students to sit and chat during the trip.

MaratonIME crew is very popular, so popular that they have friends at every SPSU institute. Like everyone else from this university, they need to take the bus after a long day learning how to fix the Wi-Fi network. Because they don't practice sports like rowing, every SPSU student sits right after entering the bus, making pairs whenever possible. Thinking about that, Gi, an ICPC expert, comes with a problem to think on the way to the subway: given a number n which indicates the number of institutes at SPSU and n integers a_i representing the amount of people waiting for the bus at the institute i, Gi wants to know for m pairs l_j, r_j (l_j ≤ r_j) if all the people waiting for the bus at any point between l_j e r_j (inclusive) took an empty bus, they could sit together in pairs (nobody would sit alone).

Input

The input consist in one line with two integers n and m, the number of institutes and the number of Gi's questions. In the second line there are n integers a_i, the number of people waiting for the bus at the i^th institute. Then follows m lines with two integers each, l_i and r_i, the first and last institute of Gi's question.

• 1 ≤ n, m ≤ 10⁵
• 0 ≤ a_i ≤ 10⁵
• 1 ≤ l_i ≤ r_i ≤ n

Output

Output "Sim" if it is possible to organize all the pairs in a way nobody sits alone or "Nao" otherwise.

ExampleInput

5 2
1 4 10 3 2
3 5
2 3

Output

Nao
Sim

Note

In the first sample we have 5 institutes with 1, 4, 10, 3 and 2 students. Gi asks if it is possible to form only couples if the ones between the 3^rd and the 5^th institutes takes an empty bus and the ones between the 2^nd and the 3^rd. For the first we have 15 so we can't and for the second we have 14 so we can.