题目描述

请帮助小鸟 Faby 穿过依次排列的 $n$ 对管道，并找到一条到达终点的最短飞行路线。

为简化问题，将 Faby 看作平面上的一个点，并假设每根管道的宽度均为 $0$。于是，每对管道之间的缺口可以表示为位于某个横坐标处的一条竖直线段。

小鸟从点

出发，目标是到达点

请寻找一条从 $s$ 到 $t$ 的最短折线路径，使其按照横坐标递增的顺序依次穿过所有给定的竖直区间。

样例 2 示意图

图中红色线段表示需要穿过的区间，黑色折线表示一条最短路径。Faby 和黑点表示样例输出中的点。点 $(2,1)$ 也可以被额外输出。

输入格式

输入包含：

• 第一行四个整数 $x_s,y_s,x_t,y_t$（$-10^9\le x_s,y_s,x_t,y_t\le 10^9$），表示起点和终点。
• 第二行一个整数 $n$（$0\le n\le 10^6$），表示区间数量。
• 接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,y_{i,1},y_{i,2}$（$-10^9\le x_i,y_{i,1},y_{i,2}\le 10^9$，且 $y_{i,1}<y_{i,2}$），表示位于横坐标 $x_i$ 处、纵坐标范围为 $[y_{i,1},y_{i,2}]$ 的竖直区间。

保证

输出格式

输出一个由 $k$ 个点组成的序列

其中 $2\le k\le n+2$。每行输出一个点的两个整数坐标。

不需要单独输出 $k$；直接逐行输出所有点，直至文件结束。

输出必须满足：

• 所有点的坐标均为整数；
• $p_1=s$，且 $p_k=t$；
• 依次连接 $p_ip_{i+1}$（$1\le i<k$）得到折线路径 $P$，则：
  • $P$ 按横坐标递增的顺序穿过所有给定区间；
  • $P$ 的总长度最短。

若存在多组合法答案，输出任意一组即可。

样例 1

输入

0 0 10 0
1
5 -10 10

输出

0 0
10 0

样例 2

输入

0 0 10 0
4
2 1 3
4 2 3
7 0 2
9 -2 -1

输出

0 0
4 2
9 -1
10 0