Rikka 偶然发现了一座无名的古老神庙及其内部地图。这座神庙包含 $n$ 个独立的房间。几条单向道路连接着这些房间，构成了一个有向无环图。

当游客进入神庙时，她会出现在第一个房间。她可以在第 $n$ 个房间找到神庙的出口。请注意，她可能无法从入口到达所有房间，同时，她也可能无法从某些内部房间逃离神庙。

所有房间都有一些宝藏。第 $i$ 个房间中宝藏的重量为 $w_i$，价值为 $c_i$。当游客到达出口时，如果她所拾取宝藏的总重量除以 $k$ 的余数等于 $t$（其中 $k$ 和 $t$ 是固定的整数），她才被允许离开神庙。

此外，有一名守护者站在某个房间里保护宝藏，但没人知道她在哪里。为了防止受到攻击，游客在任何时候都不能进入守护者所在的房间。

现在 Rikka 决定参观这座无名神庙。她将选择一条从入口到出口的路径，并拾取沿途经过的所有房间里的宝藏。她希望你计算：对于每个从 $1$ 到 $n$ 的索引 $i$，假设守护者站在第 $i$ 个房间时，她能获得的最大总价值是多少，以及有多少种方式可以达到该价值。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ ($2 \le n \le 10^5$)，表示房间数量，以及 $m$ ($0 \le m \le 2 \times 10^5$)，表示单向道路的数量。

接下来的 $n$ 行描述所有房间。第 $i$ 行包含两个整数 $w_i$ 和 $c_i$ ($1 \le w_i, c_i \le 10^9$)。

接下来的 $n$ 行描述所有道路。第 $i$ 行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，描述了一条从第 $u$ 个房间到第 $v$ 个房间的单向道路。

最后一行包含两个整数 $k$ 和 $t$ ($0 \le t < k \le 100$)，它们是离开神庙的条件系数。

输入保证单个测试用例中的所有道路都是不同的，所有测试用例中 $n$ 的总和不超过 $10^6$，且所有测试用例中 $m$ 的总和不超过 $2 \times 10^6$。

输出格式

对于每个测试用例，输出 $n$ 行。在第 $i$ 行中，我们考虑守护者站在第 $i$ 个房间的情况。如果 Rikka 没有合法的路径从入口访问到出口，则在该行输出 $-1$。否则，在该行输出两个空格分隔的整数，其中第一个是她能获得的最大总价值，第二个是她选择路径以达到最佳结果的不同方案数。第一个数字应以精确形式输出，第二个数字应在模 $(10^9 + 7)$ 下输出。

样例

样例输入 1

1
4 5
1 2
2 3
3 4
4 2
1 2
1 3
2 4
3 4
1 4
5 3

样例输出 1

-1
8 1
-1
-1