Poly DAG Judgment

You are given a layered directed acyclic graph (DAG) with d layers. Nodes in the DAG are assigned global indices in increasing order by layer. The DAG satisfies the following:

For a node \(u\) (which is not in the first layer) with incoming edges from a multiset \(S_u\) (note that multiple edges are counted separately), its associated polynomial \(F_u(x)\) satisfies \[ F_u(x)=\sum_{v\in S_u}\Bigl(F_v\bigl(x^2\bigr)^2\Bigr), \] which comes from the following operations performed when a "brilliant shard" (represented by a polynomial) travels across an edge:

• No Limit: the polynomial is squared, i.e. from \(F(x)\) to \(F(x)^2\).
• Continuity of Civilization: the polynomial is transformed by replacing \(x\) with \(x^2\); that is, from \(F(x)^2\) to \(F(x^2)^2\).
• Night Terror: when two shards meet, they fuse into one by addition.

In summary, if a shard travels from a node \(v\) to a node \(u\), its contribution is \(\bigl(F_v(x^2)\bigr)^2\). Nodes in the first layer have their polynomials provided as input. For a given query with parameters \(u\) and an execution point \(k\), if the shard left at node \(u\) is \(F_u(x)\), then the final electrical discharge is \(F_u(k)\) (computed modulo the prime \(7340033\), which equals \(2^{20}\times7+1\)).

Formal Problem Statement

You are given a layered DAG with d layers. Nodes in layer i only have edges going to nodes in layer i+1 (1-based layers). There may be multiple (parallel) edges. For each node \(u\) not in the first layer, if \(S_u\) is the multiset of nodes in the previous layer that have an edge to \(u\), then \[ F_u(x)=\sum_{v\in S_u}\left(F_v(x^2)\right)^2. \] For nodes in the first layer, the polynomial \(F_u(x)\) is given. Then, each query gives a node \(u\) and an integer \(k\) (the execution point), and you are to output \(F_u(k) \bmod 7340033\>.

inputFormat

The input is given as follows:

1. An integer d denoting the number of layers.
2. For the first layer:
   • An integer n1 denoting the number of nodes in layer 1.
   • Then for each node \(u=1\) to \(n1\), a line containing an integer deg (the degree of the polynomial) followed by deg+1 integers representing the coefficients \(a_0, a_1, \dots, a_{deg}\) of \(F_u(x)=a_0+a_1 x+\cdots+a_{deg} x^{deg}\). (All coefficients are given modulo 7340033.)
3. For layers 2 through d (for each layer i from 2 to d):
   • An integer ni denoting the number of nodes in layer i.
   • An integer mi denoting the number of directed edges from layer i-1 to layer i.
   • Then mi lines follow, each containing two integers u v. Here, u is the global index of a node in layer i-1, and v is the local index (1-indexed) of a node in layer i. The global index of a node in layer i is defined as the sum of n1+n2+...+ni-1 plus its local index.
4. An integer Q representing the number of queries.
5. Then Q lines follow, each containing two integers u k, where u is a global node index (1-indexed) and k is the execution point.

It is guaranteed that the graph is layered, and that for every node (except in layer 1) at least one edge points to it (remember that multiple edges are allowed and each edge is counted separately).

outputFormat

For each query, output a single integer: the value of \(F_u(k)\) modulo 7340033.

sample

2
2
1 1 2
0 3
1
3
1 1
2 1
1 1
2
3 1
3 2

27
171