Functions are an important concept in various programming languages. With the help of functions, we can always decompose complex tasks into relatively simple subtasks until they are refined into very simple basic operations, thereby making the organization of code more rigorous and orderly. However, excessive function calls can also lead to additional overhead, affecting the execution efficiency of the program.

A certain database application provides several functions to maintain data. It is known that the functionality of these functions can be divided into three categories:

1. Add a value to a specified element in the data;
2. Multiply every element in the data by the same value;
3. Execute a sequence of function calls in order, ensuring that no recursion occurs (i.e., no function will call itself directly or indirectly).

When using this database application, a user can input a sequence of functions to be called at once (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, Little A encountered difficulties while using this database program to process data: due to frequent and inefficient function calls, the system became unresponsive during operation, and he had to force the database program to terminate. To calculate the correct data, Little A consulted the software documentation and learned the specific functional information of each function. Now, he would like you to help him calculate what the updated data should be based on this information.

Input

The first line contains a positive integer $n$, representing the number of data elements.

The second line contains $n$ integers, where the $i$-th integer represents the initial value of the data at index $i$, denoted as $a_i$.

The third line contains a positive integer $m$, representing the number of functions provided by the database application. The functions are numbered from $1$ to $m$.

In the next $m$ lines, the first integer of the $j$-th line ($1 \le j \le m$) is $T_j$, representing the type of function $j$:

1. If $T_j = 1$, the next two integers $P_j$ and $V_j$ represent the index of the element to perform the addition on and the value to be added, respectively;
2. If $T_j = 2$, the next integer $V_j$ represents the value by which all elements are multiplied;
3. If $T_j = 3$, the next positive integer $C_j$ represents the number of functions that function $j$ will call, followed by $C_j$ integers $g_1^{(j)}, g_2^{(j)}, \dots, g_{C_j}^{(j)}$ representing the indices of the functions called in order.

The $(m+4)$-th line contains a positive integer $Q$, representing the length of the input function operation sequence.

The $(m+5)$-th line contains $Q$ integers $f_i$, where the $i$-th integer represents the index of the $i$-th function to be executed.

Output

Output a single line of $n$ space-separated integers, representing the value of each element in the database after executing the input function sequence, in the order of indices $1 \sim n$. The answer should be taken modulo $998244353$.

Examples

Input 1

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

Output 1

6 8 12

Note 1

Function 1 adds 1 to the value of $a_1$. Function 2 multiplies all elements by 2. Function 3 calls function 1 first, then function 2.

The final function sequence executes function 2 first, and all element values become $2, 4, 6$.

Then, when executing function 3, it first calls function 1, and all element values become $3, 4, 6$. Then it calls function 2, and all element values become $6, 8, 12$.

Input 2

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

Output 2

36 282 108 144 180 216 504 288 324 360

Input 3

(See call/call3.in in the contestant's directory)

Output 3

(See call/call3.ans in the contestant's directory)

Constraints

For all data: $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_k^{(j)} \le m$, $1 \le f_i \le m$.