[POI2005]Sko-knight

Knights

一个骑士在无限棋盘上移动。每种移动可以用一个向量 $(a,b)$ 描述，表示骑士可以从点 $(x,y)$ 移动到 $(x+a,y+b)$ 或 $(x-a,y-b)$。每种移动均可以在任意时刻使用任意次。

如果两个骑士从 $(0,0)$ 出发能够到达的点集完全相同，则称这两个骑士等价。对于任意骑士，都存在一个与其等价且只包含两种移动的骑士。

给定一个骑士的所有移动，请求出一个与其等价的骑士所使用的两个移动向量。

输入格式

第一行包含一个整数 $n$，表示骑士的移动种数。

接下来 $n$ 行，每行包含两个整数 $a_i,b_i$，表示一个移动向量 $(a_i,b_i)$。

输出格式

输出两行，每行包含两个整数，表示一个移动向量。

设输入的所有向量生成的整数格为 $L$，则输出的两个向量必须生成且仅生成 $L$。满足条件的任意一组向量均可，两个向量的输出顺序不限，也不限制向量的符号或所采用的等价基。

当可达点集是一维整数格时，允许其中一个输出向量为 $(0,0)$，表示不存在第二个有效生成元，但仍须输出两行。

输出的四个坐标必须是绝对值不超过 $10^9$ 的整数。除此之外，不要求对输出向量进行规范化。

样例输入

3
24 28
15 50
12 21

样例输出

0 -1
3 0

数据范围

• $3\le n\le 100$；
• $-100\le a_i,b_i\le 100$；
• 对所有 $1\le i\le n$，均有 $(a_i,b_i)\ne(0,0)$；
• 输出向量的每个坐标绝对值均不超过 $10^9$。

来源与许可

本题为 POI 2005 试题「Sko-knight」，题面与测试数据整理自 BZOJ。

样例 1

输入

3
24 28
15 50
12 21

输出

0 -1
3 0