Background

Flappy Bird is a very popular casual game.

Problem Description

In the game, the bird starts at $(0,0)$. Its goal is to reach some point whose $x$-coordinate is $X$.

Every second, you may choose to tap the screen. If you tap, the bird moves from $(x,y)$ to $(x+1,y+1)$. If you do not tap, the bird moves from $(x,y)$ to $(x+1,y-1)$.

There are also $n$ obstacles in the game, each described by a triple $(x_i,a_i,b_i)$. This means that on the vertical line $x=x_i$, the parts with $y\le a_i$ or $y\ge b_i$ are obstacles. Touching an obstacle or even just grazing its boundary is considered a failure.

Now, find the minimum number of taps needed for the bird to fly from $(0,0)$ to the destination.

Input Format

The first line contains two integers $n, X$.

The next $n$ lines each contain three integers $x_i, a_i, b_i$. The testdata guarantees that $x_i<x_{i+1}$.

Output Format

If it is impossible to reach the destination no matter what you do, output NIE. Otherwise, output the minimum number of taps.

4 11
4 1 4
7 -1 2
8 -1 3
9 0 2

5

Hint

For $100\%$ of the testdata, $0\le n\le 500000$, $1\le X\le10^9$, $0<x_i<X$, $-10^9\le a_i<b_i\le 10^9$.

Sample Explanation.

Translated by ChatGPT 5