F. Volunteering
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Artem is organizing the Championship of Kyrgyzstan in programming.

The competition will take place in the time interval [S;F].

To assist in organizing the competition, Artem has recruited n volunteers. It is known that the i-th volunteer will be able to help in the time interval [bi, ei].

Artem understands that anything can happen, so for each moment t in time, he introduced the "help index" H(t) — the number of volunteers who can help him solve various problems at time t.

Formally, the help index H(t) is equal to the number of volunteers such that bi ≤ t ≤ ei.

Artem is considering various scenarios, so for each value h [1... n], he wants to know the total time during the championship when the help index H(t) will be strictly less than h.

Input

The first line contains an integer n (1 ≤ n ≤ 3·105) — the number of volunteers.

The second line contains integers S and F (1 ≤ S < F ≤ 109) — the start and end of the time interval of the championship.

Each of the next n lines contains two integers bi and ei (1 ≤ bi < ei ≤ 109) — the start and end of the time segment when the i-th volunteer is available.

Output

Output n numbers t1, t2, ..., tn, where th is the total time during the championship when the "help index" is strictly less than h.

Example
Input
5
10 20
5 12
16 19
15 25
8 14
13 17
Output
0 3 9 10 10
Note

First test example

  • The help index will never be 0 during the championship; hence t1 = 0.
  • The help index 1 will be in the intervals [12;13], [14;15], and [19;20] — the total duration of the intervals is 3; hence t2 = 3 + 0 = 3.
  • The help index 2 will be in the intervals [10;12], [13;14], [15;16], and [17;19] — the total duration is 6; hence t3 = 6 + 3 + 0 = 9.
  • The help index 3 will be in the interval [16;17] — the total duration is 1; hence t4 = 1 + 6 + 3 + 0 = 10.
  • The help index will never be equal to 4, so t5 = 10 similarly to t4.