Connect the Points

题意翻译

平面上给定 $3$ 个点（其横坐标与纵坐标的绝对值均不超过 $10^9$），现在要在这个平面上连若干条平行于坐标轴的线段，每连一条线段，花费为该线段长。求一种连线段的方法使得这 $3$ 个点均连通且花费尽可能小。 我们定义两个点 $A,B$ 连通如下： 存在一组点 $P_0 , P_1, \ldots, P_k $，使得 $P_0$ 与 $A$ 重合，$P_k$ 与 $B$ 重合，且对于任意 $0 < i \le k$，都有 $p_i$ 与 $p_{i-1}$ 在同一条已连的线段中。 另外，保证满足题意的所有线段端点的横坐标与纵坐标的绝对值均不超过 $10^9$。

题目描述

You are given three points on a plane. You should choose some segments on the plane that are parallel to coordinate axes, so that all three points become connected. The total length of the chosen segments should be the minimal possible. Two points $ a $ and $ b $ are considered connected if there is a sequence of points $ p_0 = a, p_1, \ldots, p_k = b $ such that points $ p_i $ and $ p_{i+1} $ lie on the same segment.

输入输出格式

输入格式

The input consists of three lines describing three points. Each line contains two integers $ x $ and $ y $ separated by a space — the coordinates of the point ( $ -10^9 \le x, y \le 10^9 $ ). The points are pairwise distinct.

输出格式

On the first line output $ n $ — the number of segments, at most 100. The next $ n $ lines should contain descriptions of segments. Output four integers $ x_1 $ , $ y_1 $ , $ x_2 $ , $ y_2 $ on a line — the coordinates of the endpoints of the corresponding segment ( $ -10^9 \le x_1, y_1, x_2, y_2 \le 10^9 $ ). Each segment should be either horizontal or vertical. It is guaranteed that the solution with the given constraints exists.

输入输出样例

输入样例 #1

1 1
3 5
8 6

输出样例 #1

3
1 1 1 5
1 5 8 5
8 5 8 6

说明

The points and the segments from the example are shown below.