Emma's Switches 2
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 0.5 seconds
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_ith light switch and moves towards highernumbered switches, toggling every p_ith 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 spaceseparated integers: N, the number of light switches, and D, the number of days before Emma is expelled.
The following D lines each contain two spaceseparated 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

Sample Input 1
5 2 1 2 2 3
Sample Output 1
ON ON ON OFF OFF