{"raw_statement":[{"iden":"background","content":"“水……”\n\n在沙尘暴中跋涉许久，又整整一天没有饮水，身体已经逐渐支撑不住了。\n\n凯尔希没有拿水瓶，而是冷冷地说了一句“再撑一会”，随后就自顾自继续向前赶路。\n\n我们已经在沙暴里跋涉了多久？三个小时？还是五个小时？黄沙不停往衣物里涌，狂风则不停将沙尘甩在脸上，刮得眼睛都睁不开。但我们还不能停步，后面的萨卡兹雇佣兵还在紧追不舍，他们尽职尽责，即使是沙暴都阻挡不了他们的脚步。\n\n至于水……或许早就喝完了吧。\n\n听说沙漠里有在空水壶中灌沙来给人以希望的传统，可现在，沙子我已经喝够了，水，我只想喝口水，哪怕用身上所有的硬币去换，我也愿意。\n\n只是在这荒野里，闪亮的金属毫无意义。\n\n紧紧抱着银色的手提箱，我咬紧牙关继续迈步。\n\n耳边都是凄厉的呼啸，像是亡者的哭号，又像是鬼魂的呼唤。索恩教授或许也在其中，呼唤着我的名字？\n\n但我听不太清了。\n\n脑中满是这样的响声，已经多久了？三分钟？三小时？还是三年？\n\n沙尘遮蔽了天空，白天和黑夜已经毫无区别，时间似乎都已凝滞，只有在其中求生的人们，还在忍受着此间种种刑罚。\n\n我只是想做研究，我只是想为科学进步奉献自己的力量，而不是像现在这样，倒在沙海里风干。\n\n脑袋又酸又胀又痛，身体好像早就没了知觉，我是在行走吗，还是在看着这具名为艾利奥特的躯壳蠕动？\n\n不……思考也成为了一种奢求，现在徘徊在脑袋里的，只有一个指令：移动。\n\n移动……移动……移动……\n\n……但沙海是无垠的。\n\n“艾利奥特，张嘴。”\n\n张嘴？\n\n我下意识地放松肌肉，让嘴唇和牙齿露出一条通往口腔的通道。\n\n一串沾满沙土的果实落到了口中。\n\n有些酸涩？有些甘甜？哦，是水，是水。\n\n是水啊。\n\n……\n\n不知从什么时候开始，耳边再也没有风声，大地回复了寂静，只有阳光，沙漠，和两个在沙丘间徒步的凡人。\n\n……\n\n我望向远方，除了黄沙，还是黄沙。\n\n一眼望不到尽头，就像散落满地又被浸湿的皮鞋踩上几脚的技术文件，再也归不拢，再也理不齐。\n\n我忿忿地踢了一脚沙子，看着它们从沙丘尖端翻滚滑落，然后重新融到沙漠中，好似什么都没有发生过。\n\n沙子，沙子。\n\n我生平第一次开始痛恨沙子。\n\n“走吧，很快就能获得补给了。”\n\n凯尔希打断了我的思绪。\n\n可，很快？能有多快？\n\n一些补给？又有多少呢？\n\n呵，凯尔希从来不向人许诺希望。\n\n但至少……\n\n我似乎看见了一颗仙人掌。"},{"iden":"statement","content":"## 我们在题目描述的最下方提供了形式化题意，若您不想阅读整活部分可以直接跳到题目描述的最下方。\n\n神在猩红剧团的探索中取回了自己一部分的力量，不多，但够用。\n\n神见到了傀影。准备使用辉煌裂片对他进行审判。\n\n但是傀影躲进了一个被分成 $d$ 层的 DAG 中。\n\n具体地，DAG 上第 $i$ 层的节点只会连向第 $i+1$ 层的节点。\n\n“那就陪你继续玩玩吧。”神心想。\n\n神决定了一种审判的方式。\n\n具体地，神最开始有一些辉煌裂片。神认为，多项式具有强大的力量，所以辉煌裂片就是多项式。~~我才不告诉你是我懒得编题面。~~\n\n神有三种对辉煌裂片的操作：\n\n1. “无度”\n\n可以让辉煌裂片更加强大。具体地，对 $F(x)$ 进行这个操作就相当于令 $F(x)=F^2(x)$。\n\n2. “文明的存续”\n\n可以让“无度”后的辉煌裂片更加强大。具体地，对 $F(x)$ 进行这个操作就相当于令 $F(x)=F(x^2)$。\n\n3. “夜骇”\n\n可以让两个辉煌裂片进行融合，变得更加强大。具体地，如果对 $F(x)$ 和 $G(x)$ 进行这个操作会返回一个多项式为 $F(x)+G(x)$。\n\n神决定这样对傀影进行审判：\n\n在第一层的节点放置辉煌裂片。\n\n当辉煌裂片进入一个节点前，对自身进行“无度”。\n\n当两个辉煌裂片相遇，对这两个辉煌裂片进行“夜骇”，只会留下一个辉煌裂片为这两个辉煌裂片进行“夜骇”的结果。\n\n辉煌裂片只会在连接该节点的所有边都有辉煌裂片通过后，才会离开该节点。当辉煌裂片离开一个节点时，辉煌裂片会对进行“文明的存续”，然后分裂成若干个和原辉煌裂片相同的辉煌裂片，留下一个辉煌裂片在该节点。然后，每条边都将通过恰好一个辉煌裂片。\n\n若傀影在节点 $u$，而神有一个审判指数（execution points，EXP）$k$，该节点留下的辉煌裂片为 $F_u(x)$，那么傀影将会受到 $F_u(k)$ 伏特的电流。\n\n现在神有一些提问。每个提问类似于，若傀影藏在节点 $u$，且审判指数为 $k$，那么傀影将会受到多少伏特的电流？\n\n神是怜悯的。答案可能过大，他只要求你输出答案对 $7340033(2^{20}\\times7+1)$（一个质数）取模后的结果。\n### 形式化题意\n给你一张分为 $d$ 层的 DAG，每个节点都有一个多项式 $F_u(x)$。**可能会有重边。**\n\n这个 DAG 上第 $i$ 层的节点只会向第 $i+1$ 层的节点连边。\n\n若 $S_u$ 包含所有连向点 $u$ 的节点，那么满足 $F_u(x)=\\sum_{v \\in S_u}F_v^2(x^2)$。\n\n给出第一层节点的多项式，每次询问会给你 $u,k$，然后询问 $F_u(k)$ 对 $7340033(2^{20}\\times7+1)$（一个质数）取模后的结果。\n\n**请注意，重边算作一条边。**"},{"iden":"input","content":"第一行一个整数 $d$，表示 DAG 的层数。\n\n接下来一行会有 $d$ 个整数，第 $i$ 个数 $n_i$ 表示第 $i$ 层有 $n_i$ 个节点。\n\n接下来 $n_1$ 行，第 $i$ 行有若干个数表示第一层的 $i$ 号节点的多项式。\n\n具体地，每行第一个数 $p$ 表示多项式的最高次，接下来 $p+1$ 个数表示这个多项式的系数，若其中第 $i$ 个数（不包括 $p$）为 $f_{i-1}$，那么该多项式为 $\\sum_{i=0}^pf_ix^i$。\n\n接下来的输入分为 $d$ 段。第 $i$ 段的开头有两个数 $m,q$ 表示第 $i$ 层有 $m$ 条边，以及神在第 $i$ 层的点中有 $q$ 个询问。\n\n接下来 $m$ 行，每行两个数 $u,v$ 表示第 $i$ 层编号为 $u$ 的点连接了第 $i+1$ 层编号为 $v$ 的点。\n\n接下来 $q$ 行每行两个整数 $u,k$ 表示神询问当傀影在第 $i$ 层编号为 $u$ 的节点上时，且审判指数为 $k$ 时，傀影受到电流的伏特对 $7340033$ 取模后的结果。"},{"iden":"output","content":"由于输出可能过大，你需要对输出加密。\n\n具体地，对于第 $k$ 层的询问，若第 $i$ 个询问的答案为 $a_i$，你只需要输出 $(k \\times \\bigoplus_{i=1}^q(q-i) \\times a_i)\\bmod 2^{32}$ 即可。\n\n请注意，输出一共 $d$ 行，每行一个数字。"},{"iden":"note","content":"- Subtask1（7pts）$1\\leq d\\leq 2$。\n- Subtask2（20pts）$1\\leq d\\leq 10,\\sum q=1$。\n- Subtask3（13pts）$n_1=2$，且时间限制为 5s。\n- Subtask4（60pts）无特殊限制。\n- Subtack5（0pts）Hack 数据。\n\n对于 $ 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$。\n\n若第 $i$ 层有 $m_i$ 条边，对于 $i\\neq d$ 保证有 $n_i