Minimum Jumps to Target Platform

You are given a collection of platforms, each represented by an interval on the x‐axis and a height.

You start on a platform at position \( (x_{start}, y_{start}) \) and wish to reach any platform at a target height \( y_{target} \) using a sequence of jumps. A jump is allowed between two distinct platforms if their x-intervals overlap, i.e., if \( x_{1} \le x'_{2} \) and \( x'_{1} \le x_{2} \). Note that you may only jump between platforms of different heights.

Determine the minimum number of jumps required to reach a platform at height \( y_{target} \). If it is impossible, output -1.

Note: The starting platform is implicitly added to the set of platforms.

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer \(T\), the number of test cases.
• For each test case:
  • The first line contains four integers: \(x_{start}\), \(y_{start}\), \(y_{target}\), and \(N\) (the number of platforms).
  • Then follow \(N\) lines, each containing three integers: \(x_{left}\), \(x_{right}\), and \(y\) (the left and right x-coordinates and the height of a platform).

outputFormat

For each test case, output a single line containing one integer — the minimum number of jumps required to reach a platform at height ( y_{target} ), or (-1) if it is impossible.## sample

2
0 0 3 3
-1 1 1
-2 0 2
0 2 3
0 0 3 3
-1 1 1
-2 0 2
0 2 4

1
-1