F. Flappy Bird
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Help the bird Faby to navigate through a sequence of $$$n$$$ pairs of pipes, by finding the shortest line he can fly on to reach his destination. For simplicity, we represent Faby as a single point in the plane and assume every pipe has width zero. This way, the gap between every pair of pipes can be represented as an interval on the $$$y$$$ axis. The bird starts out at $$$s = (x_s, y_s)$$$ and his goal is to reach $$$t = (x_t, y_t)$$$. Find the shortest line from $$$s$$$ to $$$t$$$, passing through all intervals in between in increasing order of their $$$x$$$ coordinates.

Visualisation of the second sample input. The red lines represent the intervals and the black line the shortest possible path. Faby and the black dots are the points in the output. Note that $$$(2, 1)$$$ can optionally be included in the output too.
Input

The input consists of:

  • One line with four integers $$$x_s, y_s, x_t$$$ and $$$y_t$$$ ($$$-10^9 \le x_s, y_s, x_t, y_t \le 10^9$$$), the start and end points.
  • One line with an integer $$$n\ (0 \le n \le 10^6)$$$, the number of intervals.
  • $$$n$$$ lines, the $$$i$$$th of which contains three integer $$$x_i, y_{i,1}$$$ and $$$y_{i,2}$$$ ($$$-10^9 \le x_i, y_{i, 1}, y_{i, 2} \le 10^9$$$, $$$y_{i, 1} \lt y_{i, 2}$$$), the intervals.
It can be assumed that $$$x_s \lt x_1 \lt \dots \lt x_n \lt x_t$$$.
Output

Output a sequence of $$$k$$$ $$$(2 \le k \le n+2$$$) points $$$p_1, \dots, p_k$$$, one per line, such that:

  • All points have integer coordinates.
  • $$$p_1 = s$$$ and $$$p_k = t$$$.
  • Let $$$P$$$ be the path obtained by connecting $$$\overline{p_i p_{i+1}}$$$ for all $$$1 \le i \lt k$$$. Then:
    • $$$P$$$ passes through all intervals in increasing order of their $$$x$$$ coordinates.
    • The length of $$$P$$$ is minimal.
If there are multiple valid solutions, you may output any one of them.
Examples
Input
0 0 10 0
1
5 -10 10
Output
0 0
10 0
Input
0 0 10 0
4
2 1 3
4 2 3
7 0 2
9 -2 -1
Output
0 0
4 2
9 -1
10 0