P8323 "JROI-4" Phantom and the Crimson Lone Diamond

“Water…” After trekking through the sandstorm for a long time, and going a whole day without drinking, my body was gradually unable to hold on. Kal’tsit did not take out a water bottle. She only said coldly, “Hold on a bit longer,” and then kept moving forward on her own. How long have we been trudging in the sandstorm? Three hours? Or five hours? Yellow sand kept pouring into our clothes, and the gale kept flinging sand into our faces, scraping so hard that we could not even open our eyes. But we still could not stop, because the Sarkaz mercenaries behind us were still chasing closely. They were dutiful; even a sandstorm could not stop their steps. As for water… maybe we had finished it long ago. I heard that in the desert there is a tradition of filling an empty kettle with sand to give people hope. But now, I have already drunk enough sand. Water—I just want a sip of water. Even if I had to trade all the coins on me, I would be willing. It is just that in this wilderness, shiny metal means nothing. Holding the silver suitcase tightly, I clenched my teeth and kept stepping forward. In my ears were only piercing howls, like the wailing of the dead, or the calling of ghosts. Perhaps Professor Thorns was also among them, calling my name? But I could not hear clearly anymore. My head was full of those sounds. How long has it been? Three minutes? Three hours? Or three years? The dust covered the sky. Day and night had no difference anymore. Time seemed to have frozen; only those struggling to survive within it were still enduring all kinds of punishment here. I only wanted to do research. I only wanted to contribute my strength to scientific progress, not to collapse in this sea of sand and dry up. My head was sour, swollen, and aching. My body seemed to have lost all feeling long ago. Am I walking, or am I watching this body called Elliot wriggle? No… even thinking has become a luxury. Now the only command wandering in my mind is: move. Move… move… move… …But the sea of sand is endless. “Elliot, open your mouth.” Open my mouth? Subconsciously I relaxed my muscles, letting my lips and teeth open a passage into my mouth. A string of fruits covered in sand fell into my mouth. A bit sour? A bit sweet? Oh, it is water. It is water. It is water. … At some point, there was no longer any wind in my ears. The earth returned to silence. There was only sunlight, the desert, and two ordinary people walking between the dunes. … I looked into the distance. Besides yellow sand, there was still only yellow sand. It stretched beyond sight, like technical documents scattered all over the floor, then soaked and stepped on a few times by leather shoes—never to be gathered up again, never to be sorted again. Angrily I kicked a pile of sand, watching it roll and slide down from the tip of the dune, then merge back into the desert, as if nothing had happened. Sand, sand. For the first time in my life, I began to hate sand. “Let’s go. We will get supplies soon.” Kal’tsit interrupted my thoughts. But soon? How soon is “soon”? Some supplies? How much? Heh, Kal’tsit never promises people hope. But at least… I think I saw a cactus.

## We provide a formal statement at the bottom of the Description. If you do not want to read the roleplay part, you can directly jump to the bottom of the Description. God retrieved a part of His power during the exploration of the Crimson Troupe. Not much, but enough. God met Phantom, and prepared to judge him with Brilliant Shards. However, Phantom hid in a DAG that is divided into $d$ layers. Specifically, nodes in layer $i$ of the DAG only have edges pointing to nodes in layer $i+1$. “Then I will keep playing with you,” God thought. God decided on a way to carry out the judgment. Specifically, God initially has some Brilliant Shards. God believes that polynomials have great power, so Brilliant Shards are polynomials. ~~I am not telling you it is because I am too lazy to make up the story.~~ God has three operations on Brilliant Shards: 1. “No Degree” It can make a Brilliant Shard stronger. Specifically, applying this operation to $F(x)$ is equivalent to setting $F(x)=F^2(x)$. 2. “Continuation of Civilization” It can make the Brilliant Shard after “No Degree” even stronger. Specifically, applying this operation to $F(x)$ is equivalent to setting $F(x)=F(x^2)$. 3. “Night Terror” It can merge two Brilliant Shards and make them stronger. Specifically, applying this operation to $F(x)$ and $G(x)$ returns a polynomial $F(x)+G(x)$. God judges Phantom in the following way: Place Brilliant Shards on the nodes in the first layer. Before a Brilliant Shard enters a node, it applies “No Degree” to itself. When two Brilliant Shards meet, apply “Night Terror” to these two Brilliant Shards. Only one Brilliant Shard remains, which is the result of applying “Night Terror” to the two. A Brilliant Shard will only leave a node after Brilliant Shards have passed through all edges connected to that node. When a Brilliant Shard leaves a node, it applies “Continuation of Civilization,” then splits into several Brilliant Shards identical to the original one, leaving one Brilliant Shard at that node. Then, each edge will be passed through by exactly one Brilliant Shard. If Phantom is at node $u$, and God has an execution points (EXP) $k$, and the Brilliant Shard left at that node is $F_u(x)$, then Phantom will be struck by an electric current of $F_u(k)$ volts. Now God has some queries. Each query is like: if Phantom is hiding at node $u$, and the execution points is $k$, then how many volts of current will Phantom receive? God is merciful. The answer may be too large, so you only need to output the result modulo $7340033(2^{20}\times7+1)$ (a prime). ### Formal Statement You are given a DAG divided into $d$ layers. Each node has a polynomial $F_u(x)$. **There may be multiple edges.** In this DAG, nodes in layer $i$ only have edges to nodes in layer $i+1$. Let $S_u$ contain all nodes that have edges pointing to node $u$. Then it holds that $F_u(x)=\sum_{v \in S_u}F_v^2(x^2)$. You are given the polynomials of the nodes in the first layer. Each query gives $u,k$, and asks for $F_u(k)$ modulo $7340033(2^{20}\times7+1)$ (a prime). **Please note that multiple edges count as one edge.**

The first line contains an integer $d$, representing the number of layers of the DAG. The next line contains $d$ integers. The $i$-th number $n_i$ indicates that there are $n_i$ nodes in layer $i$. The next $n_1$ lines describe the polynomials of the nodes in the first layer. In the $i$-th line, there are several numbers representing the polynomial of node $i$ in the first layer. Specifically, the first number in each line is $p$, the highest degree of the polynomial. The next $p+1$ numbers are the coefficients of the polynomial. If the $i$-th of these numbers (excluding $p$) is $f_{i-1}$, then the polynomial is $\sum_{i=0}^pf_ix^i$. The remaining input is divided into $d$ blocks. At the beginning of block $i$, there are two numbers $m,q$, meaning there are $m$ edges from layer $i$, and God has $q$ queries among the nodes in layer $i$. The next $m$ lines each contain two numbers $u,v$, indicating that the node numbered $u$ in layer $i$ connects to the node numbered $v$ in layer $i+1$. The next $q$ lines each contain two integers $u,k$, indicating that God asks: when Phantom is at node $u$ in layer $i$, and the execution points is $k$, output the volts of current Phantom receives modulo $7340033$.

Since the output may be too large, you need to encrypt the output. Specifically, for the queries in layer $k$, if the answer to the $i$-th query is $a_i$, you only need to output $(k \times \bigoplus_{i=1}^q(q-i) \times a_i)\bmod 2^{32}$. Note that there are exactly $d$ lines of output, one number per line.

- Subtask 1 (7 pts): $1\leq d\leq 2$. - Subtask 2 (20 pts): $1\leq d\leq 10,\sum q=1$. - Subtask 3 (13 pts): $n_1=2$, and the time limit is 5 s. - Subtask 4 (60 pts): no special restrictions. - Subtask 5 (0 pts): hack testdata. For $100\%$ of the testdata, $1\leq\sum n