帮助小鸟 Faby 穿过一系列 $n$ 对管道，找到它飞往目的地所能经过的最短路径。为简化起见，我们将 Faby 看作平面上的一个点，并假设每根管道的宽度为零。这样，每对管道之间的缝隙就可以表示为 $y$ 轴上的一个区间。小鸟从 $s = (x_s, y_s)$ 出发，目标是到达 $t = (x_t, y_t)$。请找到一条从 $s$ 到 $t$ 的最短折线，使其按 $x$ 坐标递增的顺序穿过中间所有的区间。

图 F.1：第二个样例输入的示意图。红线表示区间，黑线表示最短路径。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_s < x_1 < \dots < x_n < x_t$。

输出格式

输出一个包含 $k$ ($2 \le k \le n + 2$) 个点的序列 $p_1, \dots, p_k$，每行一个点，满足： 所有点的坐标均为整数。 $p_1 = s$ 且 $p_k = t$。 令 $P$ 为连接所有 $p_i p_{i+1}$ ($1 \le i < k$) 得到的路径。则： $P$ 按 $x$ 坐标递增的顺序穿过所有区间。 * $P$ 的长度最短。

如果存在多个合法的解，你可以输出其中任意一个。

样例

样例输入 1

0 0 10 0
1
5 -10 10

样例输出 1

0 0
10 0

样例输入 2

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

样例输出 2

0 0
4 2
9 -1
10 0