POVISICE

문제

Mirko is a proud founder of a big software company. Initially he was the only worker in the company, but as the business grew, company hired N additional workers, one by one. We will denote Mirko with integer 0, and each of the remaining worker with integers 1 to N in order they were hired. 

On the first day of work every worker was assigned as a subordinate to another worker. Also, every worker was assigned with initial salary. However, if the salary of the new worker was greater than the salary of his boss, then his boss also got a raise to equal their salaries. If the boss of the new worker now has a greater salary than his boss, the procedure is repeated until every worker has a salary that is less than or equal to the salary of his boss. 

Write a program that will determine the number of workers that got a raise during the process of hiring each new worker. 

입력

The first line contains one integer N (1 ≤ N ≤ 300000), the number of workers. 

The second line contains one integer M, Mirko's initial salary. 

The next N lines contain two integers each I and B, initial salary of the new worker and the index of his boss. Workers are given in the order they were hired, i.e. in ascending order of their indices. 

All salaries are integers between 1 and 10⁹ and boss indices always denote a worker that was already hired at that moment. 

출력

Output N integers, one per line, the total number of workers that got a raise during the process of hiring each new worker in order they were hired. 

7
5000
4500 0
6000 0
4000 1
5500 3
7000 4
6300 2
6300 2

0
1
0
2
4
1
0