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。

null