On a faraway planet, strange plants with two stems can be found. Every plant on the planet can be
described by three numbers: the x-coordinates of the stems and
, and the height
at which the
stems are connected. The image depicts a plant with
,
and
.
Every day a new plant grows on the planet. The plant that grows on day 1 is of height , and every
subsequent plant is one higher than the previous one.
When a stem of a new plant intersects the horizontal segment of another plant, a small flower grows (if one wasn't there already). If segments merely touch in a point, a flower will not grow there. The following images are a visualization of the first example on the next page.
Write a program that, given the coordinates of all plants, calculates the number of new flowers every day.
Input Specification
The first line contains an integer
, the number of days.
Each of the following
lines contains two integers
and
, the coordinates of
the stems of a plant.
Output Specification
Output lines, the number of new flowers after each plant grows.
Sample Input 1
4
1 4
3 7
1 6
2 6
Sample Output 1
0
1
1
2
Sample Input 2
5
1 3
3 5
3 9
2 4
3 8
Sample Output 2
0
0
0
3
2
Comments