相对位置

题目描述

坐标平面上有 $N$ 个人，编号为 $1$ 到 $N$。

1 号人在原点。

给你 $M$ 条如下形式的信息：

从 $A_i$ 的视角看，$B_i$ 位于正 $x$ 方向 $X_i$ 个单位、正 $y$ 方向 $Y_i$ 个单位处。

确定每个人的坐标。如果某人的坐标无法唯一确定，报告这一情况。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$
$A_1$ $B_1$ $X_1$ $Y_1$
$\vdots$
$A_M$ $B_M$ $X_M$ $Y_M$

输出格式

输出 $N$ 行。

如果第 $i$ 个人的坐标无法唯一确定，第 $i$ 行应输出 undecidable。

如果可以唯一确定为 $(s_i,t_i)$，第 $i$ 行应依次输出 $s_i$ 和 $t_i$，用空格分隔。

样例

3 2
1 2 2 1
1 3 -1 -2

0 0
2 1
-1 -2

3 2
2 1 -2 -1
2 3 -3 -3

0 0
2 1
-1 -2

5 7
1 2 0 0
1 2 0 0
2 3 0 0
3 1 0 0
2 1 0 0
3 2 0 0
4 5 0 0

0 0
0 0
0 0
undecidable
undecidable

同一信息可能被给出多次，也可能有多个人位于同一坐标。

数据范围

• $1 \le N \le 2\times 10^5$
• $0 \le M \le 2\times 10^5$
• $1 \le A_i, B_i \le N$
• $A_i \neq B_i$
• $-10^9 \le X_i, Y_i \le 10^9$
• 所有输入值均为整数。
• 给出的信息是一致的。