동치인 기사의 이동

기사(knight)는 무한한 체스판 위를 움직인다. 기사가 할 수 있는 각 이동은 정수 쌍으로 표현된다. 쌍 $(a, b)$ 는 칸 $(x, y)$ 에서 칸 $(x+a, y+b)$ 또는 칸 $(x-a, y-b)$ 로 이동할 수 있음을 뜻한다. 각 기사는 이런 쌍들의 고정된 집합을 가진다. 모든 기사에 대해, $(0, 0)$ 에서 한 번의 이동으로 도달할 수 있는 칸들이 모두 한 직선 위에 있지는 않다고 가정한다.

두 기사가 동치(equivalent) 라는 것은, $(0, 0)$ 에서 출발하여 (여러 번 이동해서라도) 정확히 같은 칸들의 집합에 도달할 수 있음을 뜻한다. 동치인 두 기사가 어떤 칸에 도달하는 데 필요한 이동 횟수는 서로 다를 수 있다. 모든 기사에 대해, 단 두 개의 정수 쌍만으로 이동이 표현되는 동치 기사가 존재함이 알려져 있다.

기사가 $(0, 0)$ 에서 도달할 수 있는 칸들의 집합은, 기사의 이동 벡터들이 생성하는 정수 격자(lattice)와 정확히 일치한다. 따라서 두 기사가 동치일 필요충분조건은 이동 벡터들이 같은 격자를 생성하는 것이며, 이 문제는 그 격자의 두 벡터 기저(basis)를 구하는 것이다. 그런 기저는 유일하지 않으므로, 아래에 정의된 하나의 표준(canonical) 기저를 출력해야 한다.

주어진 기사의 이동 쌍들에 대해, 생성된 격자의 에르미트 표준형(Hermite Normal Form, HNF) 기저를 이루는 두 쌍 $(a, b)$ 와 $(c, d)$ 를 출력한다. 이는 다음 조건을 만족하며 입력의 이동들과 같은 격자를 생성하는 유일한 벡터 쌍이다.

• $c = 0$
• $a > 0$ 이고 $d > 0$
• $0 \le b < d$

이 조건을 만족하는 표준 기저는 항상 유일하게 존재한다.

첫째 줄에 기사의 이동을 표현하는 쌍의 개수 $n$ 이 주어진다 ($3 \le n \le 100$). 이어지는 $n$ 개의 줄에는 각각 공백으로 구분된 두 정수 $a_i$ 와 $b_i$ 가 주어진다 ($-100 \le a_i, b_i \le 100$, $(a_i, b_i) \ne (0, 0)$). 이 벡터들이 모두 한 직선 위에 있지는 않음이 보장된다.

두 줄을 출력한다. 첫째 줄에는 첫 번째 HNF 벡터인 두 정수 $a$ 와 $b$ 를, 둘째 줄에는 두 번째 HNF 벡터인 두 정수 $c$ 와 $d$ 를 각각 공백으로 구분하여 출력한다. 정의에 의해 $c = 0$, $a > 0$, $d > 0$, $0 \le b < d$ 가 성립한다. 이 표준 기저는 유일하며 입력과 같은 격자를 생성한다. 즉 입력의 기사와 동치인 기사를 나타낸다. $1 \le a \le 100$ 이고 $1 \le d \le 20000$ 임이 보장된다.