Minimum Falling Time

You are given n horizontal platforms in a 2-dimensional space. The i-th platform has a height \(h_i\) and extends from \(l_i\) to \(r_i\). They are mutually non-overlapping (i.e. their horizontal segments are disjoint). Starting from the left endpoint of the \(s\)-th platform, you want to reach the \(t\)-th platform in the minimum possible time.

The movement rules are as follows:

• You can move horizontally on the current platform at a cost of 1 unit time per unit distance.
• If you are at an endpoint of a platform and attempt to move further in that same direction, you will fall vertically. During the fall, for every unit of vertical distance you drop, you incur 1 unit of time.
• When falling from an endpoint at \(x\), you land on the first platform below (i.e. the one with the maximum height \(h_j\) such that \(h_j < h_i\) and \(l_j \le x \le r_j\)). The landing position on that platform is exactly at \(x\). Once landed, you may then move horizontally to one of the endpoints before dropping further if needed.

If it is impossible to get from the \(s\)-th platform to the \(t\)-th platform, output -1.

Note on formulas: The horizontal moving cost is the absolute difference between positions. The falling (vertical) cost from platform \(i\) to platform \(j\) is \(h_i - h_j\). For example, if you drop from \(x\) on platform \(i\) with \(h_i\) onto platform \(j\) with \(h_j\) where \(l_j \le x \le r_j\), the total cost for the drop and the subsequent move to an endpoint of platform \(j\) (say, to \(l_j\)) is: \[ \text{cost} = (h_i - h_j) + |x - l_j| \]

inputFormat

The first line contains three integers: n, s, and t (\(1 \le n \le 10^3\)). Here, s is the starting platform index and t is the target platform index.

Each of the next n lines contains three integers \(h_i\), \(l_i\), and \(r_i\) describing the height and the left and right endpoints of the \(i\)-th platform. It is guaranteed that the platforms’ horizontal intervals are disjoint.

outputFormat

Output a single integer indicating the minimum time required to reach the t-th platform from the left endpoint of the s-th platform. If it is impossible, output -1.

sample

3 1 3
10 2 5
5 1 6
0 0 7

12