{"raw_statement":[{"iden":"statement","content":"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.\n\nWhen 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.\n\nAll 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.\n\nBesides, 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.\n\nNow 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.\n\nThe input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 1000$), the number of test cases.\n\nFor each test case, the first line contains two integers $n$ ($2 <= n <= 10^5$), the number of rooms, and $m$ ($0 <= m <= 2 times 10^5$), the number of one-way roads.\n\nThe following $n$ lines describe all rooms. The $i$-th of them contains two integers $w_i$ and $c_i$ ($1 <= w_i, c_i <= 10^9$).\n\nThen following $n$ lines describe all roads. The $i$-th of them contains two integers $u$ and $v$ ($1 <= u, v <= n$) which describes a one-way road from the $u$-th room to the $v$-th room.\n\nThe last line contains two integers $k$ and $t$ ($0 <= t < k <= 100$) which are the coefficients for the condition to leave the temple. \n\nThe 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$.\n\nFor 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)$.\n\n"},{"iden":"input","content":"The input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 1000$), the number of test cases.For each test case, the first line contains two integers $n$ ($2 <= n <= 10^5$), the number of rooms, and $m$ ($0 <= m <= 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 <= w_i, c_i <= 10^9$).Then following $n$ lines describe all roads. The $i$-th of them contains two integers $u$ and $v$ ($1 <= u, v <= 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 <= t < k <= 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$."},{"iden":"output","content":"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)$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ be the number of rooms, $ m \\in \\mathbb{Z} $ the number of directed edges.  \n- Let $ G = (V, E) $ be a directed acyclic graph (DAG) with $ V = \\{1, 2, \\dots, n\\} $, $ E \\subseteq V \\times V $, $ |E| = m $.  \n- Let $ w_i \\in \\mathbb{Z}^+ $, $ c_i \\in \\mathbb{Z}^+ $ denote the weight and value of treasure in room $ i $, for $ i \\in V $.  \n- Let $ k \\in \\mathbb{Z}^+ $, $ t \\in \\mathbb{Z} $ with $ 0 \\le t < k $ be fixed modulo parameters.  \n- For each $ i \\in V $, let $ G_{-i} = (V \\setminus \\{i\\}, E') $ be the subgraph induced by removing vertex $ i $ and all incident edges.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 1000 $  \n2. $ 2 \\le n \\le 10^5 $, $ 0 \\le m \\le 2 \\times 10^5 $ per test case  \n3. $ 1 \\le w_i, c_i \\le 10^9 $ for all $ i \\in V $  \n4. $ 1 \\le k < 100 $, $ 0 \\le t < k $  \n5. Sum of all $ n $ across test cases $ \\le 10^6 $  \n6. Sum of all $ m $ across test cases $ \\le 2 \\times 10^6 $  \n7. $ G $ is a DAG with no multiple edges.  \n8. The entrance is room $ 1 $, the exit is room $ n $.  \n\n**Objective**  \nFor each $ i \\in \\{1, \\dots, n\\} $:  \n- Compute the maximum total value $ V_i^* $ and the number of paths $ P_i $ (mod $ 10^9 + 7 $) from room $ 1 $ to room $ n $ in $ G_{-i} $, such that the total weight $ W $ of collected treasures satisfies $ W \\equiv t \\pmod{k} $.  \n- If no such path exists in $ G_{-i} $, output $ -1 $.  \n- Otherwise, output $ V_i^* $ and $ P_i $.  \n\n**Formal Output Requirement**  \nFor each $ i \\in \\{1, \\dots, n\\} $, define:  \n$$\n\\mathcal{P}_i = \\left\\{ p \\in \\text{Paths}_{G_{-i}}(1 \\to n) \\,\\middle|\\, \\sum_{j \\in p} w_j \\equiv t \\pmod{k} \\right\\}\n$$\n$$\nV_i^* = \\max_{p \\in \\mathcal{P}_i} \\sum_{j \\in p} c_j, \\quad P_i = |\\mathcal{P}_i| \\mod (10^9 + 7)\n$$  \nOutput $ (V_i^*, P_i) $ for each $ i $, or $ -1 $ if $ \\mathcal{P}_i = \\emptyset $.","simple_statement":"You are given a directed acyclic graph with n rooms and m one-way roads.  \nYou start at room 1 and must reach room n.  \nEach room i has a treasure with weight w_i and value c_i.  \nYou can only collect treasures from rooms you pass through on your path.  \nTo exit, the total weight of collected treasures must have remainder t modulo k.  \nOne room i is blocked (guardian is there) — you cannot enter it.  \nFor each i from 1 to n, find:  \n- The maximum total value you can get if room i is blocked.  \n- The number of paths achieving that maximum value (mod 10^9+7).  \nIf no valid path exists, output -1.","has_page_source":false}