#P3381. 「CSP-S 2020」函数调用

「CSP-S 2020」函数调用

题目描述

函数是各种编程语言中一项重要的概念,借助函数,我们总可以将复杂的任务分解成一个个相对简单的子任务,直到细化为十分简单的基础操作,从而使代码的组织更加严密、更加有条理。然而,过多的函数调用也会导致额外的开销,影响程序的运行效率。

某数据库应用程序提供了若干函数用以维护数据。已知这些函数的功能可分为三类:

  1. 将数据中的指定元素加上一个值;
  2. 将数据中的每一个元素乘以一个相同值;
  3. 依次执行若干次函数调用,保证不会出现递归(即不会直接或间接地调用本身)。

在使用该数据库应用时,用户可一次性输入要调用的函数序列(一个函数可能被调用多次),在依次执行完序列中的函数后,系统中的数据被加以更新。 某一天,小 A 在应用该数据库程序处理数据时遇到了困难:由于频繁而低效的函数调用,系统在执行操作时进入了无响应的状态,他只好强制结束了数据库程序。为了计算出正确数据,小 A 查阅了软件的文档,了解到每个函数的具体功能信息,现在他想请你根据这些信息帮他计算出更新后的数据应该是多少。

输入格式

输入文件名为 call.in

第一行一个正整数 nn,表示数据的个数。

第二行 nn 个整数,第 ii 个整数表示下标为 ii 的数据的初始值为 aia_i

第三行一个正整数 mm,表示数据库应用程序提供的函数个数。函数从 1m1\ldots m 编号。

接下来 mm 行中,第 jj1jm1 \le j \le m)行的第一个整数为 TjT_j,表示 jj 号函数的类型:

  1. Tj=1T_j = 1,接下来两个整数 Pj, VjP_j,~V_j 分别表示要执行加法的元素的下标及其增加的值;
  2. Tj=2T_j = 2,接下来一个整数 VjV_j 表示所有元素所乘的值;
  3. Tj=3T_j = 3,接下来一个正整数 CjC_j 表示 jj 号函数要调用的函数个数,随后 CjC_j 个整数 g1(j), g2(j), , gCj(j)g_1^{(j)},~g_2^{(j)},~\ldots,~g_{C_j}^{(j)},依次表示其所调用的函数的编号。

m+4m + 4 行一个正整数 QQ,表示输入的函数操作序列长度。

m+5m + 5QQ 个整数 fif_i,第 ii 个整数表示第 ii 个执行的函数的编号。

输出格式

输入文件名为 call.out

一行 nn 个用空格隔开的整数,按照下标 1n1\ldots n 的顺序,分别输出在执行完输入的函数序列后,数据库中每一个元素的值。答案对 998244353\boldsymbol{998244353} 取模。

3
1 2 3
3
1 1 1
2 2
3 2 1 2
2
2 3

6 8 12

10
1 2 3 4 5 6 7 8 9 10
8
3 2 2 3
3 2 4 5
3 2 5 8
2 2
3 2 6 7
1 2 5
1 7 6
2 3
3
1 2 3

36 282 108 144 180 216 504 288 324 360

样例 3

见附加文件中的 [call3.in](file:call3.in) / [call3.ans](file:call3.ans)。

数据范围与提示

测试点编号 n,m,Qn,m,Q\le Cj\sum C_j 其他特殊限制
121\sim 2 10001000 =m1=m-1 函数调用关系构成一颗树
343\sim 4 100\le 100
565\sim 6 2000020000 40000\le 40000 不含第 22 类函数或不含第 11 类函数
77 =0=0
898\sim 9 =m1=m-1 函数调用关系构成一颗树
101110\sim 11 2×105\le 2\times 10^5
121312\sim 13 10510^5 不含第 22 类函数或不含第 11 类函数
1414 =0=0
151615\sim 16 =m1=m-1 函数调用关系构成一颗树
171817\sim 18 5×105\le 5\times 10^5
192019\sim 20 106\le 10^6

对于所有数据:0ai1040\le a_i\le 10^4Tj{1,2,3}T_j\in \{1,2,3\}1Pjn1\le P_j\le n0Vj1040\le V_j\le 10^41gk(j)m1\le g_k^{(j)}\le m1fim1\le f_i\le m