B. Bus Problem
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A tour company in Athens wants to buy the longest possible bus, but they are afraid that the bus will not be able to move around the parked cars.

There are $$$n$$$ parallel horizontal lanes, numbered from $$$1$$$ to $$$n$$$ from top to bottom, and $$$m$$$ stationary cars. Car $$$i$$$ occupies $$$[l_i,r_i]$$$ on lane $$$k_i$$$. Cars on the same lane may touch at endpoints, but their interiors do not intersect.

A bus of positive integer length $$$b$$$ occupies $$$[x,x+b]$$$ on one lane, where $$$x$$$ may be any real number. It starts on any lane, entirely to the left of all cars, and must finish entirely to their right.

The bus may move any distance to the right along its lane, or change to an adjacent lane while keeping $$$[x,x+b]$$$ unchanged. A lane change is a single move, allowed only if the bus fits on both lanes at that position. The bus cannot move left, turn, leave the highway, or drive horizontally between lanes.

Throughout every move, the bus may touch cars at endpoints, but must not overlap a car by a positive length. Help the tour company find the maximum possible bus length.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 200\,000$$$, $$$0\le m\le 200\,000$$$), the numbers of lanes and cars.

Each of the next $$$m$$$ lines contains three integers $$$k_i$$$, $$$l_i$$$, and $$$r_i$$$ ($$$1\le k_i\le n$$$, $$$0\le l_i \lt r_i\le 10^9$$$), describing a car.

The interiors of cars on the same lane do not intersect. Cars are given in arbitrary order.

Output

Print INF if arbitrarily large bus lengths are possible. Otherwise, print the maximum possible positive integer length, or $$$0$$$ if no positive length works.

Examples
Input
2 2
1 1 3
2 6 8
Output
3
Input
3 2
1 0 100
3 0 100
Output
INF
Input
2 2
1 0 1
2 0 1
Output
0
Note

In the first example, a bus of length $$$3$$$ starts on lane $$$2$$$. When it occupies $$$[3,6]$$$, it can change to lane $$$1$$$, touching both cars at endpoints, and continue right. A longer bus cannot fit between the cars during a lane change.

In the second example, lane $$$2$$$ is empty, so any bus length works.

In the third example, the cars block both lanes over the same interval, so no bus can pass.