Emma's Switches

Emma is a massive nuisance at school by always meddling around with the light switches. Each day, she goes to toggle a selection of the school's $N$ light switches, numbered from $1$ to $N$. If the selected switch is originally on, she turns it off, and if it is originally off, she turns it on.

Emma chooses her light switches in a very particular way. For each day $i$, she starts at the $k_i$-th light switch and moves towards higher-numbered switches, toggling every $p_i$-th switch until she runs out of switches.

After $D$ days, Emma is caught and is expelled from her school. You need to find the final states of all of the school's light switches.

All switches are initially off, and you can assume that no one else touches the switches.

Input

The first line includes two space-separated integers: $N$, the number of light switches, and $D$, the number of days before Emma is expelled.

The following $D$ lines each contain two space-separated integers representing $k_i$ and $p_i$ for each day.

Output

For each light switch, output ON or OFF depending on its final state.

Constraints

• $1 \le N, D \le 50{,}000$
• $1 \le k_i \le N$
• $1 \le p_i \le 50$

Subtasks

• Subtask 1 (15%): $1 \le N, D \le 1{,}000$
• Subtask 2 (25%): $k_i = 1$ for all $i$. That is, Emma always starts by toggling switch 1 each day.
• Subtask 3 (30%): $p_i = 1$ for all $i$. That is, Emma toggles the $k_i$-th switch and every switch numbered after it each day.
• Subtask 4 (30%): No further constraints

Explanations

In the sample case, on day 1, Emma turns on the 1st switch, and then every 2nd switch after that until she runs out of switches:

ON
OFF
ON
OFF
ON

Then, on day 2, Emma starts by turning on the 2nd switch and continues by turning off the 5th switch:

ON
ON
ON
OFF
OFF

Note

Python programmers should submit solutions with Python 3.6 (PyPy 7.3) selected instead of Python 3.8, as it may make the submission run faster. We cannot guarantee that all solutions submitted for Python 3.8 will pass with the given time limit.