좌표

당신은 은하 제국의 참모다. 행성 타부에 숨어 있는 반란군 기지의 위치를 모두 알아내야 한다. 타부의 지도는 $10^8 \times 10^8$ 크기의 격자이고, 기지 하나의 위치는 $0 \le x, y < 10^8$을 만족하는 좌표 $(x, y)$로 나타낸다.

제국은 항복한 반란군을 붙잡아 기지의 위치를 심문했다. 그런데 붙잡힌 반란군은 기지 두 곳이 $x$축 방향과 $y$축 방향으로 각각 얼마나 떨어져 있는지만 말한다. 심문 결과와 모순되지 않는 모든 기지의 좌표를 구하라.

첫째 줄에 기지의 수 $N$과 붙잡힌 반란군의 수 $M$이 주어진다. ($1 \le N \le 100\,000$, $N \le M \le 1\,000\,000$)

다음 $M$개 줄에 네 정수 $a_i$, $b_i$, $dx_i$, $dy_i$가 주어진다. ($1 \le a_i, b_i \le N$, $-10^8 \le dx_i, dy_i \le 10^8$) 이는 기지 $b_i$의 $x$좌표에서 기지 $a_i$의 $x$좌표를 뺀 값이 $dx_i$이고, 기지 $b_i$의 $y$좌표에서 기지 $a_i$의 $y$좌표를 뺀 값이 $dy_i$라는 뜻이다.

심문 결과는 서로 모순되지 않으며, 이 결과만으로 모든 기지의 위치가 정해진다.

$N$개 줄에 걸쳐 $j$번 기지의 좌표 $x_j$와 $y_j$를 공백으로 구분해 출력한다.

지도 전체를 평행이동한 좌표도 심문 결과와 모순되지 않는다. 답을 하나로 정하기 위해 1번 기지를 $(0, 0)$에 둔 좌표를 출력한다. 이 규칙을 따르면 모든 좌표의 절댓값은 $10^9$ 이하이다.