#### Registered Users Only

Please login to view and utilize this feature.

## 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 exist two pigeons in the same hole

## 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, the **maximum number of pigeons** in one hole

## 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 2Output

1 2 1 1 1

## 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 9001Output

1 2 2 2 1

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 30 | 10 | 1.5s | 32MB | Minimum |

2 | 70 | 10 | 2.5s | 64MB | Minimum |

3 | 0 | 2 | 1.5s | 32MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o pigeonhole_ex -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512