考虑一个正多边形（即所有边长相等且所有内角相等的多边形），其顶点按顺时针方向依次编号为 $1$ 到 $N$。令这些顶点对应一个完全无向图的顶点，其对角线和边对应于该图的边。此外，该图的每条边都被染成黑色或白色。

如果一个生成树的所有边颜色相同，且其中任意两条边都不相交（在顶点处的交点除外），则称该生成树为合法的。

给定图的染色方案，请找出该图的任意一个合法生成树。边的颜色按以下方式给出：令整数 $C_{a,b}$ 表示顶点 $a$ 和 $b$ 之间边的颜色（$0$ 表示白色，$1$ 表示黑色，$C_{a,b} = C_{b,a}$）。对于某些点对 $(a, b)$，其颜色 $C_{a,b}$ 是显式给出的。所有其他边的颜色可以通过以下公式计算：

$$C_{a,b} = \begin{cases} 0, & \text{if } (\min(a, b) \cdot X + \max(a, b) \cdot Y) \pmod Z < P_a + P_b \\ 1, & \text{otherwise} \end{cases}$$

其中 $X, Y, Z$ 以及所有的 $P_i$ 均为已知。

输入格式

第一行包含一个整数 $N$ ($3 \le N \le 5 \cdot 10^5$)。 第二行包含一个整数 $E$ ($0 \le E \le 2 \cdot 10^5$)，表示显式给出颜色的边数。 接下来的 $E$ 行，每行包含三个整数 $a, b, c$ ($1 \le a, b \le N, 0 \le c \le 1$)，表示 $C_{a,b} = c$。 接下来一行包含整数 $X, Y$ 和 $Z$。接下来的 $N$ 行包含整数 $P_i$。 其中，$0 \le X, Y, P_i \le 10^{11}$；$1 \le Z \le 10^{11}$。

输出格式

输出 $N - 1$ 行，描述生成树的边。每行包含两个整数，表示由边连接的两个顶点。如果不存在解，则输出 “No solution”。如果存在多个解，输出其中任意一个即可。

样例

样例输入 1

4
1
2 4 0
13 17 23
5
10
7
3

样例输出 1

1 2
2 4
3 2