当前没有测试数据。

题目描述

在平面直角坐标系中，给定 N 个点与 M 个相对位置关系，其中 1 号点的坐标为 (0,0)。

第 i 个关系的格式如下：

• 给定编号 A，B 以及 X 和 Y，表示：B 号点的横坐标 X$_b$ 是 A 号点的横坐标 X$_a$ 再加 X，B 号点的纵坐标 Y$_b$ 是 A 号点的纵坐标 Y$_a$ 再加  Y ($X_b = X_a + X,Y_b = Y_a + Y$)。

通过1 号点的坐标和 M 条相对关系，可以确定某些点的坐标，也有些点可能确定不了。对于每个点，如果能确定坐标，输出坐标值，否则输出undecidable 。

输入格式

N M

$A_1 B_1 X_1 Y_1$

.

.

.

$A_M B_M X_M Y_M$

输出格式

输出 N 行答案，如果第 i 个点的坐标不能确定，输出 undecidable ，否则输出该点的坐标

样例

样例输入 #1

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

样例输出 #1

0 0
2 1
-1 -2

样例输入 #2

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

样例输出 #2

0 0
2 1
-1 -2

样例输入 #3

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

样例输出 #3

0 0
0 0
0 0
undecidable
undecidable

数据范围与提示

• 1<=N<=2*10$^5$
• 0<=M<=2*10$^5$
• 1<=A$_i$,B$_i$<=N
• A$_i$ != B$_i$
• -10$^9$ <= $X_i,Y_i$ <= 10$^9$
• 保证所有信息不产生矛盾