如果对于任意两个点,平面上的一组点至少满足以下三个条件之一,则称为良好点集:
- 这两个点位于同一水平线上;
- 这两个点位于同一垂直线上;
- 角点位于这两点的矩形在其内部或边界上至少包含该集合中除这两个点之外的一个点。我们在这里指的是边与坐标轴平行的矩形,即所谓的两点的边界框。
给定一个由平面上的 n 个点组成的集合。找到给定集合的任何好的超集,其大小不会超过 2·105 点。
输入
第一行包含一个整数 n (1 ≤ n ≤ 104) — 初始集中的点数。接下来的 n 行描述了该集合的点。每行包含两个整数 xi 和 yi (- 109 ≤ xi, yi ≤ 109) — 对应点的坐标。保证所有的点都是不同的。
输出
在第一行打印一个好的超集中的点数 m (n ≤ m ≤ 2·105),在接下来的 m 行上打印这些点。点坐标的绝对值不应超过 109。请注意,不应最小化 m,找到给定集合的任何好的超集就足够了,其大小不超过 2·105。
超集中的所有点都应具有整数坐标。
示例
输入 #1
2 1 1 2 2
输出 #1
3 1 1 2 2 1 2