题目描述

在一个平面直角坐标系上有 $n$ 个点，每个点有编号，它们间存在 $m$ 条关系，其中第 $i$ 条关系格式如下：

• 给定编号 $a_i,b_i$ 与整数 $x_i,y_i$，表示若第 $a_i$ 个点的坐标为 $(p_i,q_i)$，则满足第 $b_i$ 个点的坐标为 $(p_i+x_i,q_i+y_i)$。保证 $a_i\not =b_i$。

其中 $1$ 号点的坐标为 $(0,0)$。

你需要根据这些关系求出每个点的坐标，或输出 undecidable 以报告其中一些点的坐标无法确定。保证关系不会互相矛盾，但可能重复。

$1\le a_i,b_i\le n\le 2\times10^5$，$0\le m\le 2\times 10^5$，$-10^9\le x_i,y_i\le 10^9$。

输入格式

第一行包含两个整数 $n,m$，含义同题面。

接下来 $m$ 行，第 $i$ 行包含四个整数 $a_i,b_i,x_i,y_i$。

输出格式

输出共 $n$ 行，第 $i$ 行输出用空格分隔的两个整数表示第 $i$ 个点的坐标，若该点坐标无法确定则输出 undecidable。

样例 1

输入

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

输出

0 0
2 1
-1 -2

样例 2

输入

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

输出

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

输出

0 0
0 0
0 0
undecidable
undecidable