Intersections on Alien Plants

On a distant planet, a peculiar species of two-stemmed plants has been discovered. Each plant is described by three integers: the x-coordinates of its two stems, \(L\) and \(R\), and the connecting height \(H\). A plant with parameters \((L, R, H)\) consists of two vertical segments located at \(x=L\) and \(x=R\) (both extending from \(y=0\) to \(y=H\)), and a horizontal segment connecting them at \(y=H\).

Every day a new plant grows. The plant that grows on day \(1\) has height \(1\) and each subsequent plant has a strictly higher height than the previous one.

A small flower blooms at any point where the vertical stem of a newly grown plant intersects the horizontal segment (at height \(H_i\)) of an earlier plant \((L_i, R_i, H_i)\), except when the intersection forms a T shape. In other words, if the vertical stem meets the horizontal segment exactly at one of its endpoints (i.e. at \(x=L_i\) or \(x=R_i\)), no flower blooms at that point.

Formally, consider two plants \(i\) and \(j\) with \(H_i < H_j\). When plant \(j\) grows, its two vertical stems (at \(x=L_j\) and \(x=R_j\)) may intersect the horizontal segment of plant \(i\) (which spans \((L_i, R_i)\) at \(y=H_i\)). A flower blooms at an intersection if and only if:

[ L_i < x < R_i, \quad \text{for } x=L_j \text{ or } x=R_j. ]

Given the coordinates for all plants in the order they grow (i.e. increasing \(H\)), your task is to compute, for each day, the number of new flowers that bloom on that day.

inputFormat

The input begins with a line containing a single integer \(n\) (\(1 \le n \le 10^5\)), the number of days (plants).

Each of the following \(n\) lines contains three integers \(L\), \(R\), and \(H\) (with \(L < R\)), describing one plant. The plants are given in order of strictly increasing height \(H\) (i.e. the plant on day 1 has the smallest height, the plant on day 2 has the next height, and so on).

outputFormat

Output \(n\) lines. The \(i\)th line should contain a single integer representing the number of new flowers that bloomed on day \(i\).

sample

2
2 5 1
3 4 2

0
2