AT_abc320_d [ABC320D] Relative Position

在一个平面直角坐标系上有 $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\ \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 $ - 入力は全て整数である - 与えられる情報は矛盾しない ### Sample Explanation 1 $ 3 $ 人の位置関係は下図のようになっています。 !\[図\](https://img.atcoder.jp/abc320/787d69ac49af24e80723e88b4f954f44.png) ### Sample Explanation 2 $ 3 $ 人の位置関係は下図のようになっています。 !\[図\](https://img.atcoder.jp/abc320/5dde7e83dd268b5b5fc322ddcb44eb86.png) ### Sample Explanation 3 同じ情報が複数回与えられたり、同じ座標に複数の人がいることもあります。