C. Blaster the Daredevil
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This year, Blaster wants to make a grand exit from graduation, and what better way to do so than by launching himself out of a cannon? Blaster's stunt can be modeled as a path in the XY-plane where the cannon is positioned at the origin, $$$(0, 0)$$$, and can be aimed at any angle.

Suspended in the air are $$$n$$$ floating hoops, each represented as a vertical segment. The $$$i$$$-th hoop is located $$$x_i$$$ meters along the X-axis. The bottom of the hoop is positioned $$$a_i$$$ meters above the X-axis, and the top of the hoop is positioned $$$b_i$$$ meters above the X-axis.

Blaster, modeled as a single point, will follow a perfectly straight-line trajectory after launch (since he has conveniently disabled Earth's gravity for this stunt). He is considered to pass through a hoop if his trajectory intersects or touches at least one point on the vertical line segment between $$$(x_i, a_i)$$$ and $$$(x_i, b_i)$$$ (inclusive).

Your task is to determine the maximum number of hoops Blaster can pass through if you carefully choose the cannon's launch angle.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of hoops.

Each of the next $$$n$$$ lines contains three integers $$$x_i, a_i, b_i$$$ $$$(1 \leq x_i \leq 10^9, 0 \leq a_i \leq b_i \leq 10^9)$$$, describing the position and height range of the $$$i$$$-th hoop.

Output

Print a single integer—the maximum number of hoops Blaster can pass through for an optimal choice of launch angle.

Example
Input
5
2 1 3
4 2 5
3 1 4
5 3 6
1 2 3
Output
4