問題文

株式会社 KYOPRO-MARKET では、今日は N 個の会議が予定されています。i 番目の会議は時刻 L_i [秒] に始まり、時刻 R_i [秒] に終了します。

i=1, 2, 3, \cdots, N について、以下の問いの答えを出力してください。

問い：
i 番目の会議には絶対出席しなければならないとき、最大何個の会議に出席できるか？
ただし、会議は延長される可能性もあるので、2 つの出席する会議の間には K 秒以上空ける必要がある。

制約

• 1 \leq N \leq 100000
• 0 \leq K \leq 86400
• 0 \leq L_i < R_i \leq 86400

入力例 1

5
0
0 4
1 2
3 7
5 9
7 8

出力例 1

2
3
3
2
3

それぞれの i について、最適な会議の出席方法の一例は以下の通りになります。

• i=1 のとき：会議 1, 4 に出席する。
• i=2 のとき：会議 2, 3, 5 に出席する。
• i=3 のとき：会議 2, 3, 5 に出席する。
• i=4 のとき：会議 1, 4 に出席する。
• i=5 のとき：会議 2, 3, 5 に出席する。

入力例 2

9
1000
0 1000
1000 2000
2000 3000
3000 4000
4000 5000
5000 6000
6000 7000
7000 8000
8000 9000

出力例 2

5
4
5
4
5
4
5
4
5

会議と会議の間には K=1000 秒以上空ける必要があることに注意してください。