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.
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 n numbers t1, t2, ..., tn, where th is the total time during the championship when the "help index" is strictly less than h.
5
10 20
5 12
16 19
15 25
8 14
13 17
0 3 9 10 10
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.
