在未能成功获得 IOI 参赛资格后，Kleofáš 决定成为一名回转滑雪冠军。明天是 Kleofáš 人生中非常重要的一天：他将参加他的第一场滑雪比赛！

在比赛期间，Kleofáš 需要从起点出发到达终点，同时穿过 $n$ 个闸门。为了尽可能快，Kleofáš 希望走最短的轨迹。

题目描述

滑雪赛道可以描述为一个起点 $S$、一个终点 $F$ 和 $n$ 个闸门。每个闸门都是一条平行于 $x$ 轴（即水平）的线段。没有两个闸门位于相同的 $y$ 坐标（海拔）上。起点位于所有闸门的上方，即其 $y$ 坐标高于任何闸门的 $y$ 坐标。终点位于所有闸门的下方，也位于起点的下方。

求一条最短的折线，从点 $S$ 出发，到达点 $F$，并按从上到下的顺序穿过所有闸门。我们称折线与线段相交，当且仅当它们至少有一个公共点（该点可以是线段的端点）。

输入格式

第一行包含一个整数 $n$ ($0 \le n \le 10^6$)，表示闸门的数量。第二行包含四个整数 $x_S, y_S, x_F, y_F$，分别表示点 $S = (x_S, y_S)$ 和 $F = (x_F, y_F)$ 的坐标。

接下来 $n$ 行，第 $i$ 行包含三个整数 $x_{1i}, x_{2i}, y_i$，表示第 $i$ 个闸门是从 $(x_{1i}, y_i)$ 到 $(x_{2i}, y_i)$ 的线段。对于每个 $i$，满足 $x_{1i} < x_{2i}$。

所有坐标均在 $-10^9$ 到 $10^9$ 之间（含边界）。闸门按从上到下的顺序排列，即 $y_S > y_1 > y_2 > \dots > y_n > y_F$。

输出格式

可以证明，一定存在唯一的最短折线，且其所有顶点都具有整数坐标。输出该折线，且不包含任何冗余顶点（即仅输出折线改变方向的顶点）。

第一行输出一个整数 $k$，表示最优折线中的顶点数量。接下来输出 $k$ 行，第 $i$ 行包含两个空格分隔的整数 $x_i, y_i$，表示折线第 $i$ 个顶点的坐标。顶点必须按从起点到终点的顺序命名，因此必须满足 $x_1 = x_S, y_1 = y_S, x_k = x_F, y_k = y_F$ 且 $y_1 > y_2 > \dots > y_k$。

子任务

样例

输入 1

4
5 10 6 0
0 4 7
7 10 6
5 8 4
2 5 1

输出 1

5
5 10
4 7
7 6
5 1
6 0

说明

情况如下图所示：