Dandan is a fanatical Tetris enthusiast, but after maxing out her score, she finally began to feel bored. So, she started thinking about a simplified version of Tetris: initially, the ground is empty. Assume all blocks are rectangular, and blocks cannot be rotated or flipped. At each moment, Dandan chooses a position to drop a block. When a block hits the ground or another block during its descent, it stops on the ground or on top of that block. Landing on another block means that the lower boundary of the upper block and the upper boundary of the lower block share at least one line segment (a single point does not count).

In Tetris, if a hole is formed between blocks at any moment, it looks unappealing. Therefore, Dandan wants to know how many new holes are formed after each block is dropped. A hole is defined as a closed region with an area greater than 0, formed by the boundaries of the blocks or the ground.

Dandan tells you the height $H_i$ of each block she drops, as well as the left and right boundaries $L_i$ and $R_i$ of the drop position, for $1 \le i \le n$. She wants to know how many new holes are formed each time a block is dropped.

Input

The first line of the input contains a positive integer $n$, representing the total number of blocks dropped. The following $n$ lines each contain three integers separated by spaces, representing $L_i$, $R_i$, and $H_i$, which are the left boundary, right boundary, and height of the dropped block, respectively. The input data guarantees $0 \le L_i < R_i \le 100000$ and $H_i \le 1000$. 30% of the data guarantees $n \le 100$, and 100% of the data guarantees $n \le 100000$.

Output

The output contains $n$ lines, each with a single number. The $i$-th line represents the number of new holes formed after the $i$-th block is dropped.

Examples

Input 1

6
1 3 2
4 7 2
2 5 1
3 6 1
8 11 2
6 8 3

Output 1

0
0
1
0
0
2