Description

我们在题目描述的最下方提供了形式化题意，若您不想阅读整活部分可以直接跳到题目描述的最下方。

神在猩红剧团的探索中取回了自己一部分的力量，不多，但够用。

神见到了傀影。准备使用辉煌裂片对他进行审判。

但是傀影躲进了一个被分成 $d$ 层的 DAG 中。

具体地，DAG 上第 $i$ 层的节点只会连向第 $i+1$ 层的节点。

“那就陪你继续玩玩吧。”神心想。

神决定了一种审判的方式。

具体地，神最开始有一些辉煌裂片。神认为，多项式具有强大的力量，所以辉煌裂片就是多项式。我才不告诉你是我懒得编题面。

神有三种对辉煌裂片的操作：

1. “无度”

可以让辉煌裂片更加强大。具体地，对 $F(x)$ 进行这个操作就相当于令 $F(x)=F^2(x)$。

2. “文明的存续”

可以让“无度”后的辉煌裂片更加强大。具体地，对 $F(x)$ 进行这个操作就相当于令 $F(x)=F(x^2)$。

3. “夜骇”

可以让两个辉煌裂片进行融合，变得更加强大。具体地，如果对 $F(x)$ 和 $G(x)$ 进行这个操作会返回一个多项式为 $F(x)+G(x)$。

神决定这样对傀影进行审判：

在第一层的节点放置辉煌裂片。

当辉煌裂片进入一个节点前，对自身进行“无度”。

当两个辉煌裂片相遇，对这两个辉煌裂片进行“夜骇”，只会留下一个辉煌裂片为这两个辉煌裂片进行“夜骇”的结果。

辉煌裂片只会在连接该节点的所有边都有辉煌裂片通过后，才会离开该节点。当辉煌裂片离开一个节点时，辉煌裂片会对进行“文明的存续”，然后分裂成若干个和原辉煌裂片相同的辉煌裂片，留下一个辉煌裂片在该节点。然后，每条边都将通过恰好一个辉煌裂片。

若傀影在节点 $u$，而神有一个审判指数（execution points，EXP）$k$，该节点留下的辉煌裂片为 $F_u(x)$，那么傀影将会受到 $F_u(k)$ 伏特的电流。

现在神有一些提问。每个提问类似于，若傀影藏在节点 $u$，且审判指数为 $k$，那么傀影将会受到多少伏特的电流？

神是怜悯的。答案可能过大，他只要求你输出答案对 $7340033(2^{20}\times7+1)$（一个质数）取模后的结果。

形式化题意

给你一张分为 $d$ 层的 DAG，每个节点都有一个多项式 $F_u(x)$。可能会有重边。

这个 DAG 上第 $i$ 层的节点只会向第 $i+1$ 层的节点连边。

若 $S_u$ 包含所有连向点 $u$ 的节点，那么满足 $F_u(x)=\sum_{v \in S_u}F_v^2(x^2)$。

给出第一层节点的多项式，每次询问会给你 $u,k$，然后询问 $F_u(k)$ 对 $7340033(2^{20}\times7+1)$（一个质数）取模后的结果。

请注意，重边算作一条边。

Input Format

第一行一个整数 $d$，表示 DAG 的层数。

接下来一行会有 $d$ 个整数，第 $i$ 个数 $n_i$ 表示第 $i$ 层有 $n_i$ 个节点。

接下来 $n_1$ 行，第 $i$ 行有若干个数表示第一层的 $i$ 号节点的多项式。

具体地，每行第一个数 $p$ 表示多项式的最高次，接下来 $p+1$ 个数表示这个多项式的系数，若其中第 $i$ 个数（不包括 $p$）为 $f_{i-1}$，那么该多项式为 $\sum_{i=0}^pf_ix^i$。

接下来的输入分为 $d$ 段。第 $i$ 段的开头有两个数 $m,q$ 表示第 $i$ 层有 $m$ 条边，以及神在第 $i$ 层的点中有 $q$ 个询问。

接下来 $m$ 行，每行两个数 $u,v$ 表示第 $i$ 层编号为 $u$ 的点连接了第 $i+1$ 层编号为 $v$ 的点。

接下来 $q$ 行每行两个整数 $u,k$ 表示神询问当傀影在第 $i$ 层编号为 $u$ 的节点上时，且审判指数为 $k$ 时，傀影受到电流的伏特对 $7340033$ 取模后的结果。

Output Format

由于输出可能过大，你需要对输出加密。

具体地，对于第 $k$ 层的询问，若第 $i$ 个询问的答案为 $a_i$，你只需要输出 $(k \times \bigoplus_{i=1}^q(q-i) \times a_i)\bmod 2^{32}$ 即可。

请注意，输出一共 $d$ 行，每行一个数字。

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

• Subtask1（7pts）$1\leq d\leq 2$。
• Subtask2（20pts）$1\leq d\leq 10,\sum q=1$。
• Subtask3（13pts）$n_1=2$，且时间限制为 5s。
• Subtask4（60pts）无特殊限制。
• Subtack5（0pts）Hack 数据。

对于 $100\%$ 的数据，满足 $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$。

若第 $i$ 层有 $m_i$ 条边，对于 $i\neq d$ 保证有 $n_i<n_{i+1}\leq2\times n_i$ 和 $n_i\leq m_i\leq 3\times n_i$，且 $m_d=0,1 \leq n_1 \leq 5$。