Problem Description
The pigeonhole principle states that given n+1 pigeons and n holes and that all pigeons are put into a hole, there must exist some hole that contains at least 2 pigeons
More generally, given p pigeons and n holes, there must exist some hole with ceil(p/n) pigeons
Guan is not convinced and wants to run a program to prove this
Each run of the program will simulate p pigeons leaving or entering holes. There will be h holes, numbered from 0 to h-1
Each pigeon has a number pi and will enter the hole (pi mod h) (i.e. pi%h) when it enters
Two pigeons may not have the same number
You are required to output whether there is guaranteed to exist one hole with at least two pigeons in it.
Input
The first line of the input contains two integers, the number of operations n, and the number of holes h
For the next n lines, each line consists of an integer, either 0 or 1, 1 indicating entry and 0 indicating leaving of a pigeon. This integer is followed by another integer pi, indicating the number of the pigeon entering/leaving
No pigeon will leave before it has entered
Constraints
1<=pi<=1,000,000,000
Output
For each operation, output an integer on each line, 0 if there is no hole with at least 2 pigeons and 1 if there is at least 1 hole with at least 2 pigeons after that operation
Subtasks
Subtask 1 (30%) n,h<=2000
Subtask 2 (70%) n,h<=2000000
Sample Testcase 1
Input
5 3
1 1
1 9001
0 9001
1 2
0 2
Output
0
1
0
0
0
Explanation
Pigeon 9001 shares the same hole as pigeon 1 (hole 1) (9001%3=1), but pigeon 2 does not share the same hole as pigeon 1, hence after operation two, there are two pigeons in the same hole, but not after operation three
Sample Testcase 2
Input
5 3
1 1
1 9001
1 2
0 2
0 9001
Output
0
1
1
1
0