Emma's Switches 2

This problem is identical to Emma's Switches except that the bounds for $N$, $D$ and $p_i$ are larger, there are no partial marks, and the time limit is lower. Solving this problem in Python might not be possible.

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 100{,}000$
• $1 \le k_i \le N$
• $1 \le p_i \le 100{,}000$

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