分子由通过化学键结合在一起的原子组成。每个化学键连接两个原子。每个原子可以与多个其他原子相连，每个连接都有一个独立的化学键。分子中的所有原子都直接或间接地通过化学键相互连接。

分子的化学性质不仅取决于原子对之间如何通过化学键连接，还取决于原子在分子内的物理位置。化学键可以将原子相互拉近，因此在给定分子中所有化学键的复杂相互作用的情况下，确定原子的位置有时很困难。

给定一个分子的描述。每个化学键连接两个不同的原子，且每对原子之间最多存在一个化学键。部分原子的坐标是已知且固定的，其余原子会自然移动到使得每个原子都位于其通过化学键连接的相邻原子坐标的平均值处的位置。为简化起见，分子中的原子位于笛卡尔 $xy$ 平面上。

输入格式

输入的第一行包含两个整数 $n$ ($2 \le n \le 100$)，表示原子数量；$m$ ($n - 1 \le m \le \frac{n(n-1)}{2}$)，表示化学键数量。

接下来的 $n$ 行描述原子的位置。第 $i$ 行包含两个整数 $x, y$ ($0 \le x, y \le 1\,000$ 或 $x = y = -1$)，分别是第 $i$ 个原子的 $x$ 和 $y$ 坐标。如果两个坐标均为 $-1$，则表示该原子的位置未知。

接下来的 $m$ 行描述化学键。第 $i$ 行包含两个整数 $a$ 和 $b$ ($1 \le a < b \le n$)，表示原子 $a$ 和原子 $b$ 之间存在一个化学键。

保证至少有一个原子的位置是固定的。

输出格式

输出 $n$ 行，描述每个原子的最终位置。具体来说，在第 $i$ 行输出两个数字 $x$ 和 $y$，即第 $i$ 个原子的最终坐标。如果存在多个解，则接受其中任何一个。如果每个未知原子的坐标与其通过化学键连接的所有相邻原子的坐标平均值之差不超过 $10^{-3}$，则该解被接受。注意，多个原子共享相同的坐标是可以接受的。

样例

样例输入 1

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

样例输出 1

0 0
1 0
2 0

样例输入 2

5 4
0 0
-1 -1
-1 -1
-1 -1
4 0
1 2
2 3
3 4
4 5

样例输出 2

0 0
1 0
2 0
3 0
4 0

样例输入 3

4 3
0 0
2 0
1 1
-1 -1
1 4
2 4
3 4

样例输出 3

0 0
2 0
1 1
1 0.3333333