题目描述

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

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

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

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

输入格式

第一行 $2$ 个整数 $n$、$m$。

接下来 $m$ 行，每行 $4$ 个整数 $a_i$、$b_i$、$x_i$、$y_i$。

输出格式

输出 $n$ 行，每行两个整数，表示 $n$ 个点的坐标。若无法求出全部 $n$ 个点的坐标，则输出 undecidable。

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$