P7077 [CSP-S 2020] Function Calls

Functions are an important concept in many programming languages. With functions, we can always break a complex task into relatively simple subtasks, until they are refined into very simple basic operations, making the code more rigorous and well-organized. However, too many function calls can also cause extra overhead and affect the program’s running efficiency. A database application provides several functions to maintain data. These functions can be divided into three types: 1. Add a value to a specified element in the data. 2. Multiply every element in the data by the same value. 3. Execute several function calls **in order**, and it is guaranteed that no recursion will occur (i.e., it will not directly or indirectly call itself). When using this database application, the user can input, at one time, a sequence of functions to call (a function may be called multiple times). After executing the functions in the sequence **in order**, the data in the system is updated. One day, Xiao A ran into trouble while using this database program to process data: due to frequent and inefficient function calls, the system became unresponsive during execution, so he had to force-quit the database program. In order to compute the correct data, Xiao A consulted the software documentation and learned the detailed information of each function. Now he asks you to compute what the updated data should be based on this information.

The first line contains a positive integer $n$, denoting the number of data elements. The second line contains $n$ integers. The $i$-th integer indicates that the initial value of the data at index $i$ is $a_i$. The third line contains a positive integer $m$, denoting the number of functions provided by the database application. The functions are numbered from $1 \sim m$. In the next $m$ lines, in the $j$-th line ($1 \le j \le m$), the first integer is $T_j$, denoting the type of function $j$: 1. If $T_j = 1$, the next two integers $P_j, V_j$ denote the index of the element to be added and the value to add to it, respectively. 2. If $T_j = 2$, the next integer $V_j$ denotes the multiplier applied to all elements. 3. If $T_j = 3$, the next positive integer $C_j$ denotes the number of functions called by function $j$, followed by $C_j$ integers $g^{(j)}_1, g^{(j)}_2, \ldots , g^{(j)}_{C_j}$ in order, denoting the function numbers it calls. Line $m + 4$ contains a positive integer $Q$, denoting the length of the input function operation sequence. Line $m + 5$ contains $Q$ integers $f_i$. The $i$-th integer denotes the function number of the $i$-th executed function.

Output one line containing $n$ integers separated by spaces. In the order of indices $1 \sim n$, output the value of each element in the database after executing the input function sequence. **Take the answer modulo** $\boldsymbol{998244353}$.

**[Sample #1 Explanation]** Function $1$ adds $1$ to $a_1$. Function $2$ multiplies all elements by $2$. Function $3$ first calls function $1$, then calls function $2$. The final function sequence first executes function $2$, so all elements become $2, 4, 6$. Then when executing function $3$, it first calls function $1$, so all elements become $3, 4, 6$. Then it calls function $2$, so all elements become $6, 8, 12$. **[Constraints]** ::cute-table{tuack} | Test Point ID | $n, m, Q \le$ | $\sum C_j$ | Other Special Constraints | | :----------: | :----------: | :----------: | :----------: | | $1 \sim 2$ | $1000$ | $= m - 1$ | The function call relations form a tree. | | $3 \sim 4$ | $1000$ | $\le 100$ | None. | | $5 \sim 6$ | $20000$ | $\le 40000$ | No type $2$ functions, or no type $1$ functions. | | $7$ | $20000$ | $= 0$ | None. | | $8 \sim 9$ | $20000$ | $= m - 1$ | The function call relations form a tree. | | $10 \sim 11$ | $20000$ | $\le 2 \times 10^5$ | None. | | $12 \sim 13$ | $10^5$ | $\le 2 \times 10^5$ | No type $2$ functions, or no type $1$ functions. | | $14$ | $10^5$ | $= 0$ | None. | | $15 \sim 16$ | $10^5$ | $= m - 1$ | The function call relations form a tree. | | $17 \sim 18$ | $10^5$ | $\le 5 \times 10^5$ | None. | | $19 \sim 20$ | $10^5$ | $\le 10^6$ | None. | For all testdata: $0 \le a_i \le 10^4$, $T_j \in \{1,2,3\}$, $1 \le P_j \le n$, $0 \le V_j \le 10^4$, $1 \le g^{(j)}_k \le m$, $1 \le f_i \le m$。 Translated by ChatGPT 5