Mirko là ông chủ kiêu hãnh của một công ty phần mềm lớn. Ban đầu công ty chỉ có một mình Mirko. Công việc làm ăn phát đạt và công ty thuê ~n~ công nhân, lần lượt từng người, từng người một. Mirko được đánh số là ~0~. Các công nhân khác – đánh số từ ~1~ đến ~n~ theo trình tự thuê.

Mỗi người mới vào có một mức lương khởi điểm và chịu sự chỉ đạo của một ai đó đã có mặt trong công ty. Nếu lương công nhân cao hơn lương thủ trưởng trực tiếp của mình thì lương của người thủ trưởng đó được nâng lên bằng lương người dưới quyền mình. Quá trình điều chỉnh này được tiếp diễn cho đến khi đảm bảo được trong toàn công ty lương thủ trưởng không thấp hơn lương công nhân dưới quyền.

Yêu cầu: Với mỗi công nhân được tuyển chọn vào công ty hãy xác định số người phải điều chỉnh lương cho phù hợp với người mới được tuyển chọn.

Input

Vào từ file POVISICE.INP:

• Dòng đầu chứa số nguyên dương ~n\ (n \le 3\times 10^5)~,
• Dòng thứ 2 chứa một số nguyên – lương khởi điểm của Mirko,
• Dòng thứ ~i~ trong ~n~ dòng sau chứa 2 số nguyên ~S~ và ~B~ – lương khởi điểm và thủ trưởng của người công nhân thứ ~i~.
  • Lương khởi điểm nằm trong phạm vi từ ~1~ đến ~10^9~.

Output

Ghi ra tệp POVISICE.OUT:

• ~n~ số nguyên, mỗi số trên một dòng, là kết quả tính được đối với mỗi người.

Subtasks

• Subtask 1: ~30\%~ test có ~n \le 5000~;
• Subtask 2: ~30\%~ test có ~n \le 5\times 10^4~;
• Subtask 3: ~40\%~ test có ~n \le 3\times 10^5~;

Sample Input 1

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

Sample Output 1

0
1
0
2
4
1
0