시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 1 1 50.000%

문제

Vasya owns a magical hourglass store and he is crazy about hourglasses. Vasya wants everything in his store to work like a clock. Whenever some hourglass in his store becomes empty, Vasya immediately turns it over.

His store has $n$ hourglasses. Hourglass $i$ has sand for exactly $b_i$ minutes and will magically appear in the store $a_i$ minutes after Vasya's work day starts. Each hourglass appears empty, so Vasya has to turn it over immediately. Vasya is working for $t$ minutes every day.

Vasya is very tired of walking around his store and turning his hourglasses over and over again. So he would like to know how many hourglasses he will have to turn over at every minute from the start of his work day.

입력

First line contains two integers $n$ and $t$ --- number of hourglasses in Vasya's store and number of minutes in Vasya's work day ($1 \le n, t \le 2 \cdot 10^5$).

Next $n$ lines contain the description of Vasya's hourglasses: two integers $a_i$ and $b_i$ --- the moment when $i$-th hourglass appears, and the number of minutes it works without turning it over ($1 \le a_i, b_i \le 2 \cdot 10^5$).

출력

Output $t$ integers, where $i$-th number is equal to the number of hourglasses Vasya has to turn over after $i$ minutes pass.

서브태스크

번호 배점 제한
1 16

$n \le 5000$, $t \le 5000$

2 23

$n \le 2 \cdot 10^5$, $t \le 5000$

3 27

$n \le 2 \cdot 10^5$, $t \le 2 \cdot 10^5$, all $b_i$ are different

4 34

$n \le 2 \cdot 10^5$, $t \le 2 \cdot 10^5$

예제 입력 1

2 5
1 2
2 4

예제 출력 1

1 1 1 0 1

예제 입력 2

4 8
2 2
1 3
3 4
5 10

예제 출력 2

1 1 1 2 1 1 2 1

예제 입력 3

2 12
2 1
1 2

예제 출력 3

1 1 2 1 2 1 2 1 2 1 2 1

힌트

In the first sample Vasya has to:

  • First minute: turn the first hourglass over (first hourglass appears after 1 minute)
  • Second minute: turn the second hourglass over (second hourglass appears after 2 minutes)
  • Third minute: turn the first hourglass over again (2 minutes passed, so you have to turn it over again)
  • Fourth minute: nothing to do (first hourglass still has 1 more minute, second one --- 2 more minutes)
  • Fifth minute: turn the first hourglass over (2 minutes passed, turn it over again)

In the second sample Vasya has to:

  • First minute: turn the second hourglass over (second hourglass appears after 1 minute)
  • Second minute: turn the first hourglass over (first hourglass appears after 2 minutes)
  • Third minute: turn the third hourglass over (third hourglass appears after 3 minutes)
  • Fourth minute: turn the first and the second hourglasses over
  • Fifth minute: turn the fourth hourglass over (forth hourglass appears after 5 minutes)
  • Sixth minute: turn the first hourglass over
  • Seventh minute: turn the second and the third hourglasses over
  • Eighth minute: turn the first hourglass over

채점 및 기타 정보

  • 예제는 채점하지 않는다.