Description
Big Orange Cat (大橘) found a strange orange tree in his backyard, represented as a syntax tree with n nodes. Each node is either a number or an operator, including basic operators (+, -, *) and m custom operators.
Each custom operator (the i-th one) is defined as follows:
- oi: the symbol representing the operator.
- ki: the number of input parameters (child nodes) it accepts.
- si: the preorder traversal of the syntax tree defining its computation rule, consisting only of +, -, *, and numbers.
In the syntax tree, parameters are denoted as A (first parameter), B (second parameter), and so forth. For example:
The custom operator @(A, B) computes (A + B) * (A - B), represented by the preorder traversal * + A B - A B.
Given the expression @ 10 13, where A = 10 and B = 13, it expands to * + 10 13 - 10 13, calculating as (10 + 13) * (10 - 13) = 23 * (-3) = -69.
The syntax tree can be visualized as:
- The expanded form of @ (top).
- The tree with A = 10 and B = 13 substituted (bottom).
Next, there are q operations, and each operation can be one of the following:
- Given index, change the value or symbol of a node at positions index in the initial syntax tree’s preorder traversal.
-
Given index1 and index2, swap the subtrees of the nodes at positions index1 and index2 in the initial syntax tree’s preorder traversal. Note that after swapping the two nodes, their indices will also be swapped. Refer to the diagram below for clarification.
- Output the result of the syntax tree after calculation.
Input
The first line contains three integers: n, m, and q, which represent the total number of nodes, the number of custom operators, and the number of operations, respectively.
The next m lines describe the custom operators. Each line includes:
- A character oi: the symbol of the i-th custom operator.
- A positive integer ki: the number of input parameters it takes.
- A string si: the preorder traversal result of the syntax tree created by this operator’s rule, made up of numbers and operators (including +, -, *), with each operator or number separated by a space.
Next line contains a string representing the syntax tree’s preorder traversal result, with each element separated by a space.
The following q lines represent q operations, where each operation can be one of these:
1 index symbol: Change the symbol of the node at position index to symbol.2 index num: Change the number of the node at position index to num.3 index1 index2: Swap the subtrees of the nodes at positions index1 and index2.4: Output the result of the current syntax tree after calculation, modulo 109 + 7.
Constraints
- 1 <= n <= 104
- 0 <= m <= 10
- 1 <= q <= 105
- t and si are made up of numbers and visible characters, and si will not contain other custom operators.
- 1 <= | si | <= 150
- oi will be a visible character other than
+, -, or* - All numbers are between [0, 109].
- ki = 2
- The number of type 4 operations (output results) is <= 100.
Subtasks
- testcase 1: m = 0, q = 1, and only the fourth operation is present.
- testcase 2: m = 0, and there are no third operations.
- testcases 3 ~ 5: m = 0.
- testcase 6: q = 1, and only the fourth operation is present.
- testcase 7: There are no third operations.
- testcases 8 ~ 10: No additional constraints.
Output
Whenever the operation 4 is encountered, output the result of the current syntax tree after calculation, modulo 109 + 7. If the result after applying 109 + 7 is negative, add 109 + 7 to it before outputting. You can refer to Example 2: the original calculation result is -69, and after adding $10^9 + 7$, it becomes 999999938.
Explanation of Sample Test Case 3:
