题目描述

给定 $n$ 个点与 $m$ 个关系，第 $i$ 个关系的格式如下：

• 给定编号 $x$，$y$ 以及 $a$ 和 $b$，设 $x$ 点在平面直角坐标系的位置为 $(x,y)$，则 $y$ 点在平面直角坐标系的位置为 $(x+a,y+b)$。

其中 $1$ 号点的坐标为 $(0,0)$，现在你需要根据这 $m$ 条关系求出这 $n$ 个点的坐标。

但是这 $m$ 条关系有时会重复，还有时求不出所有点的坐标，这时候你需要输出 undecidable。

输入格式

第一行输入 $N$ $M$

接下来 $M$ 行每行输入四个整数分别嗲表 $A_i$ $B_i$ $X_i$ $Y_i$

输出格式

一共输出 $N$ 行。

• 若无法确定某个人的坐标，输出 undecidable
• 否则输出两个空格隔开的整数代表第 $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\ \leq\ N\ \leq\ 2\times\ 10^5$
• $0\ \leq\ M\ \leq\ 2\times\ 10^5$
• $1\leq\ A_i,\ B_i\ \leq\ N$
• $A_i\ \neq\ B_i$
• $-10^9\ \leq\ X_i,Y_i\ \leq\ 10^9$

样例 1 解释

下图显示了三个人的位置关系。

样例 2 解释

下图显示了三个人的位置关系。