Birds' Breakfast Problem

In an infinite grid jungle, each cell initially contains exactly one worm at time \(0\). There are \(n\) birds. The \(i\)-th bird starts at cell \((x_i, y_i)\) at time \(0\), with the guarantee that either \(x_i=1\) or \(y_i=1\) (and the starting cell will never be \((1,1)\)). Moreover, if a bird flies downward then its starting row is \(1\), and if a bird flies right then its starting column is \(1\>.

Each bird flies in a fixed direction: a bird starting on the first row will fly downward (i.e. increasing its row by 1 each time unit) and a bird starting on the first column will fly right (i.e. increasing its column by 1 each time unit). At time \(0\), when a bird is at its starting cell, it eats the worm in that cell. Thereafter, at each time unit, every bird that is still in flight moves one cell in its respective direction. If upon arriving at a cell the worm has already been eaten (by some other bird at an earlier time), the arriving bird becomes displeased and immediately stops moving (and remains in that cell for the rest of the process).

The breakfast time is limited to \(W\) time units. Thus, any bird that has not stopped flying by the start of time \(W\) is forcibly stopped before moving at time \(W\>.

It is guaranteed that at any moment in time, no two birds share the same cell. Your task is to determine, for each bird \(i\) \((1\le i\le n)\), how many worms it has eaten by the time it stops.

Note: All formulas are rendered in LaTeX format.

inputFormat

The first line contains two integers \(n\) and \(W\) \( (1\le n \le \text{small},\; 1\le W \le \text{small})\) representing the number of birds and the time limit respectively.

Then \(n\) lines follow. The \(i\)-th line contains two integers \(x_i\) and \(y_i\) representing the starting row and column of the \(i\)-th bird. It is guaranteed that for each \(i\), either \(x_i=1\) or \(y_i=1\), and \((x_i,y_i)\) is not \((1,1)\).

outputFormat

Output \(n\) lines. The \(i\)-th line should contain a single integer, the number of worms eaten by the \(i\)-th bird in the order of input.

sample

2 5
1 2
3 1

2
5