問題文

株式会社 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$

入力例 1Copy

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

出力例 1Copy

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$ に出席する。

入力例 2Copy

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

出力例 2Copy

5
4
5
4
5
4
5
4
5

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