A ground station tracks a constellation of satellites. Each satellite pass guarantees a fixed bandwidth capacity over a half-open interval of minutes [start, end) -- covering every minute from start up to, but not including, end.

For any minute covered by at least one satellite, the effective bandwidth at that minute is the average of the capacities of every satellite covering it, using integer floor division. A minute covered by zero satellites has no effective bandwidth and must be left out of the report entirely. Whenever a maximal run of consecutive covered minutes has the same effective bandwidth throughout a sub-range, those minutes must be reported as a single merged band rather than split into smaller pieces; a band never spans across an uncovered gap even if the effective bandwidth on both sides happens to match.

Given all satellite passes, output the resulting bands in order of increasing start minute.

Input format

The first line contains a single integer n, the number of satellite passes. Each of the next n lines contains three integers start_i, end_i, capacity_i describing one pass, with start_i < end_i.

Output format

First print a single integer m, the number of bands. Then print m lines, each with three integers: the band's start minute (inclusive), end minute (exclusive), and its effective bandwidth, in order of increasing start minute.

Constraints

1 <= n <= 10^5 0 <= start_i < end_i <= 10^9 1 <= capacity_i <= 10^9

2
1 4 2
3 9 4

3
1 3 2
3 4 3
4 9 4

3
0 2 4
2 4 4
6 8 4

2
0 4 4
6 8 4