Problem Description

Rikka discovered an unnamed ancient temple together with its internal map by accident. The temple contains $n$ separated rooms. Several one-way roads connect these rooms and form a directed acyclic graph.

When a visitor enters the temple, she will appear in the first room. she can find the exit of the temple in the $n$-th room. Notice that she probably cannot arrive all rooms from the entrance and meanwhile, she may not have the chance to escape the temple from some room inside.

All rooms have some treasures. The weight of the treasure stored in the $i$-th room is $w_i$, and its value is $c_i$. A visitor, when she arrives at the exit, is allowed to leave the temple if the remainder of the total weight of treasures she has picked divided by $k$ is equal to $t$ where $k$ and $t$ are fixed integers.

Besides, a guardian is standing in a room and protecting the treasure, but no one knows where she is. To prevent being attacked, visitors should not step into the room of the guardian at any time.

Now Rikka decides to visit the unnamed temple. She will select a path from the entrance to the exit, picking treasures in all rooms she will pass through. She wants you to calculate, for each index $i$ from $1$ to $n$, what the maximum total value she can obtain is and in how many ways she could achieve that, in case the guardian is standing in the $i$-th room.

Input Format

The input contains several test cases, and the first line contains a single integer $T$ ($1 \le T \le 1000$), the number of test cases.

For each test case, the first line contains two integers $n$ ($2 \le n \le 10^5$), the number of rooms, and $m$ ($0 \le m \le 2 \times 10^5$), the number of one-way roads.

The following $n$ lines describe all rooms. The $i$-th of them contains two integers $w_i$ and $c_i$ ($1 \le w_i, c_i \le 10^9$).

Then following $n$ lines describe all roads. The $i$-th of them contains two integers $u$ and $v$ ($1 \le u, v \le n$) which describes a one-way road from the $u$-th room to the $v$-th room.

The last line contains two integers $k$ and $t$ ($0 \le t < k \le 100$) which are the coefficients for the condition to leave the temple.

The input guarantees that all roads in a single test case are distinct, the sum of $n$ in all test cases is at most $10^6$, and the sum of $m$ in all test cases is at most $2 \times 10^6$.

Output Format

For each test case, output $n$ lines. In the $i$-th line, we consider the case when the guardian is standing in the $i$-th room. If there is no valid path for Rikka to visit the temple from the entrance to the exit, output $-1$ in this line. Otherwise, output two space-separated integers in this line, where the first one is the maximum total value she can obtain, and the second one is the number of different paths she can select to achieve the best result. The first number should be outputted in exact form, while the second one should be outputted in modulo $(10^9 + 7)$.

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

-1
8 1
-1
-1