在一个未知的大城市中寻找目的地可能会充满挑战，特别是对于像 Kirk 这样总是试图走最短路径的计算机科学家来说。规划可以提供帮助——给定城市地图，Kirk 希望找到他的当前位置与目的地之间的最短路径。

城市地图可以在平面上表示为一个由单位正方形组成的无限网格。

Kirk 目前位于正方形 $(0, 0)$，他的目的地是正方形 $(X, Y)$。

城市中有 $N$ 栋建筑物。每栋建筑物都是一个完全占据若干单位正方形的矩形。任意两栋建筑物都不会接触或重叠，也就是说，Kirk 可以自由地在每栋建筑物周围行走。一栋建筑物通过指定其占用的两个对角顶点正方形的坐标来定义。

在每一步中，Kirk 可以走到四个相邻正方形之一，但他不允许步入被建筑物占领的正方形。他的当前位置位于城市的西入口，且每个被建筑物占领的正方形的 $x$ 坐标都严格大于零。

编写一个程序，在给定建筑物位置的情况下，寻找一条从 Kirk 当前位置到其目的地的最短路径。路径应报告为一系列垂直和水平线段，且任意两条相邻线段不平行。路径的长度是路径中包含的正方形数量，不包括初始正方形。

输入格式

输入的第一行包含两个整数 $X, Y$ ($1 \le X \le 10^6$, $-10^6 \le Y \le 10^6$) —— 目的地正方形的坐标。

输入的第二行包含一个整数 $N$ ($0 \le N \le 100\,000$) —— 城市中建筑物的数量。

接下来的 $N$ 行，每行包含四个整数 $X_1, Y_1, X_2, Y_2$ ($1 \le X_1, X_2 \le 10^6$, $-10^6 \le Y_1, Y_2 \le 10^6$) —— 被建筑物占领的两个对角顶点正方形的坐标。

输出格式

输出的第一行应包含一个整数 $L$ —— 到达目的地的最短路径长度。

输出的第二行应包含一个整数 $M$ —— 最短路径中的线段数量。线段数量 $M$ 不能超过 $1\,000\,000$。

接下来的 $M$ 行，每行应包含两个整数 $DX$ 和 $DY$，描述 Kirk 在一个线段中的相对移动。对于每个线段，值 $DX, DY$ 中有且仅有一个应为零，且任意两条相邻线段不能平行。

注意：如果存在多个解，您可以输出其中任意一个。

子任务

对于未完全正确或不完整的解法，如果其正确找到了最短路径的长度，将获得部分分数。

如果最小长度正确，您将获得对应测试点 $80\%$ 的分数。

如果您选择仅寻找最小长度，则无需输出其他任何内容（即只需输出 $L$）。

样例

输入格式 1

9 1
2
5 -3 8 3
10 -3 13 3

输出格式 1

16
3
0 4
9 0
0 -3

输入格式 2

12 0
5
2 -1 3 1
6 -7 8 -1
6 1 8 6
4 3 4 5
10 -5 10 3

输出格式 2

24
8
0 -2
4 0
0 2
5 0
0 4
2 0
0 -4
1 0

说明

样例 1 对应的输入与解

样例 2 对应的输入与解

每个图示描绘了相应的输入以及所提供的解。