Description

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.

Input Format

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$.

Output Format

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.

3
1 2 2
1 1 1

2 1
1 1
1 2
1 3

3 2
1 1
1 2
2 2
2 5
1 36

0 2
1 7
2 6

0
1352
10488222
//下面是加密前的输出
4
676
1682209
3496074
4354184

Hint

• 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<5060$, $1\leq d\leq 10$, $\sum q\leq 1.5 \times 10^6$, $1\leq w,k<7340033$, $0 \leq p \leq 2$.

If layer $i$ has $m_i$ edges, then for $i\neq d$ it is guaranteed that $n_i<n_{i+1}\leq2\times n_i$ and $n_i\leq m_i\leq 3\times n_i$, and $m_d=0,1 \leq n_1 \leq 5$.

Translated by ChatGPT 5