无限平面上有 $$$n$$$ 个点。第 $$$i$$$ 个点的坐标为 $$$(x_i, y_i)$$$,使得 $$$x_i > 0$$$ 且 $$$y_i > 0$$$。坐标不一定是整数。
您只需一步即可执行以下操作:
- 选择两个点 $$$a$$$ 和 $$$b$$$ ($$$a \neq b$$$);
- 将点 $$$a$$$ 从 $$$(x_a, y_a)$$$ 移动到 $$$(x_a + 1, y_a)$$$ 或 $$$(x_a, y_a + 1)$$$;
- 将点 $$$b$$$ 从 $$$(x_b, y_b)$$$ 移动到 $$$(x_b + 1, y_b)$$$ 或 $$$(x_b, y_b + 1)$$$;
- 删除点 $$$a$$$ 和 $$$b$$$。
但是,只有存在一条穿过 $$$a$$$ 新坐标、$$$b$$$ 新坐标和 $$$(0, 0)$$$ 的线时,才能执行移动。
否则,无法执行移动,并且点分别保持在其原始坐标 $$$(x_a, y_a)$$$ 和 $$$(x_b, y_b)$$$ 处。
删除某些点后,点的编号不会改变。一旦点被移除,它们就无法在以后的移动中被选择。请注意,在移动过程中必须移动两个点,不能将它们保留在原始坐标处。
您最多可以执行多少步?这些动作是什么?
如果有多个答案,您可以打印其中任何一个。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 点数。
接下来的 $$$n$$$ 行的第 $$$i$$$ 包含四个整数 $$$a_i, b_i, c_i, d_i$$$ ($$$1 \le a_i, b_i, c_i, d_i \le 10^9$$$)。第 $$$i$$$ 点的坐标为 $$$x_i = \frac{a_i}{b_i}$$$ 和 $$$y_i = \frac{c_i}{d_i}$$$。
输出
在第一行中打印一个整数 $$$c$$$ — 您可以执行的最大移动次数。
接下来的每一行 $$$c$$$ 都应包含对移动的描述:两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \neq b$$$) - 在当前移动期间删除的点。应该有一种方法可以根据语句移动点 $$$a$$$ 和 $$$b$$$,以便有一条线穿过 $$$a$$$ 的新坐标、$$$b$$$ 的新坐标和 $$$(0, 0)$$$。在以后的移动中不能选择删除的点。
如果有多个答案,您可以打印其中任何一个。您可以按任意顺序打印棋步和棋步中的分数。
示例
输入 #1
7 4 1 5 1 1 1 1 1 3 3 3 3 1 1 4 1 6 1 1 1 5 1 4 1 6 1 1 1
输出 #1
3 1 6 2 4 5 7
输入 #2
4 2 1 1 1 1 1 2 1 2 1 1 2 1 2 1 2
输出 #2
1 1 2
输入 #3
4 182 168 60 96 78 72 45 72 69 21 144 63 148 12 105 6
输出 #3
1 2 4
注意
以下是第一个示例中为移动选择的点数和移动: