Little $\Omega$ came up with a data structure problem, so he first constructed a tree with node weights:

Given a tree of size $n$, with nodes labeled $1$ to $n$, the parent of node $i \in [2, n]$ is denoted as $f_i \in [1, i-1]$. Additionally, each node $i$ has a weight $a_i$. Initially, the weights are determined by the input; see the Input section for details.

In a data structure problem, there must be corresponding modification and query operations. The two simplest non-trivial operations on a tree are path addition and path summation.

Therefore, you need to support the following two operations:

0 x y v: Add $v$ to the weights of all nodes on the simple path between $x$ and $y$ in the tree.

1 x y: Query the sum of the weights of all nodes on the simple path between $x$ and $y$ in the tree.

After creating the problem, Little $\Omega$ showed it to Little N, who remarked:

"...This is too simple, isn't this just a template problem for Heavy-Light Decomposition?!!"

Little $\Omega$ then recalled the principle of trading space for time that he learned when he first started OI, so he decided that the memory limit for this problem is 64 MB.

Input

The first line contains three positive integers $id, n, q$, where $id$ is the subtask ID, and four non-negative integers $A, B, C, a_0$.

$A, B, C, a_0$ are used to generate the node weights $a_1, a_2, \dots, a_n$ using the following recurrence relation:

$$a_i=(Aa_{i-1}^2 + Ba_{i-1}+C) \bmod 2^{32}$$

The next line contains $n-1$ positive integers representing $f_2, \dots, f_n$.

The next $q$ lines each contain several integers, in the form 0 x' y' v' or 1 x' y', representing a modification or a query.

Here, $x', y', v'$ are used for forced online processing. The actual operations use $x=x' \operatorname{xor} P, y = y' \operatorname{xor} P, v = v' \operatorname{xor} P$, where $\operatorname{xor}$ is the bitwise XOR operator ^ in C/C++, and $P = \mathrm{lastans} \operatorname{\&} (2^{20}-1)$, where $\mathrm{lastans}$ is the answer to the previous query (if there is no previous query, it is $0$), and $\operatorname{\&}$ is the bitwise AND operator & in C/C++.

Output

Output the result of each query modulo $2^{32}$ on a new line.

Examples

Input 1

0 10 10 935995202 406705156 7034169 418665824
1 1 1 1 1 1 1 7 2
0 10 3 781084039
1 7 5
0 897574 897583 833116301
1 897583 897572
0 886189 886179 123805569
1 886182 886190
1 145142 145136
1 854537 854538
1 896515 896525
0 879409 879412 746499584

Output 1

2925376046
3681387943
4240586487
2878147072
2350755335
731736886

Examples 2-15

See the provided files.

Subtasks

Each set of sample data corresponds to the constraints and properties of its respective subtask ID (except when the subtask ID is $0$). To avoid potential constant factor issues, it is guaranteed that the provided samples (for subtask IDs other than $0$) have the same generation strength as the test cases used in the final evaluation.

In the "Tree Shape" column, A means $f_i$ is generated uniformly at random in $[1, i-1]$ for all $i \in [2, n]$; B means $f_i=i-1$ for all $i \in [2, n]$; C means there are no special restrictions on the tree shape.

In the "Special Property" column, X means there are no modification operations; Y means $x=y$ for every modification operation; Z means $x=y$ for every query operation; W means no special properties.

For $100\%$ of the data, $1 \leq n \leq 7 \times 10^6$, $0 \leq q \leq 5 \times 10^4$, $1 \leq f_i < i$, $1 \leq x, y \leq n$, $0 \leq A, B, C, a_0, v \leq 10^9$.

Note

The input size for this problem is large; you may need to use efficient input methods to avoid time limit exceeded errors. For fairness, a fast I/O template is provided (refer to fast_input.cpp in the provided files). Notes on this template:

1. The provided fast input template occupies about 1 MB of space. A larger parameter $S$ increases speed but also increases memory usage; please determine $S$ carefully based on your actual situation to achieve the best space-time balance.
2. Ensure that there are no variables, functions, or namespaces named INPUT_SPACE or inn in your code to avoid naming conflicts, which would cause compilation errors. Similarly, statements like #define gc getchar() might conflict with internal naming in INPUT_SPACE. If such compilation errors occur, you need to change these aliases.
3. It is recommended to use file input for this template. Input from the keyboard may lead to situations where the program cannot terminate; in such cases, you must manually input a character equivalent to the end-of-file character at the end of the input (this character cannot be directly adjacent to the input numbers; it is recommended to put it on a new line). For example, on Windows, this character is Ctrl+Z.
4. For C and C++ users, this template requires including stdio.h and cstdio (or bits/stdc++.h) respectively.
5. For efficiency and code length considerations, the inn() function can only be used to input an unsigned 32-bit integer.

A sample program demonstrating the fast input template and weight generation is provided in sample.cpp in the provided files.

Warnings regarding the memory limit:

1. The program itself may occupy about 2–4 MB of space (e.g., included libc libraries); please avoid having your memory usage too close to the limit.
2. The provided fast input template occupies about 1 MB of space. Increasing the parameter $S$ can reduce the number of fread calls (thereby speeding up slightly), or you can use your own input method.
3. Note that while recursive calls do not explicitly occupy much space, the recursion stack can consume memory (you can simply understand it as the program needing to record parameters and return values for the recursion). For example, a recursive function taking an int parameter and returning an int that calls itself 100 times might incur space overhead equivalent to defining 200 int variables (the exact ratio depends on compiler implementation and optimization). Since the "memory limit" for evaluation is the peak memory usage during program execution, excessive recursion depth may lead to MLE. Please use recursion cautiously unless you can ensure your recursion depth will not be too large.
4. Due to the underlying implementation of outputting to files (e.g., buffering output in memory), the output process itself may consume some space. For the output scale of this problem, you can assume this part will not exceed 1 MB; however, some debug output (e.g., using cerr or outputting to stderr) may generate additional space overhead (even though it does not appear in the output file and thus does not affect the evaluation comparison), so ensure your final submission does not contain excessive debug output.
5. You are solely responsible for any consequences of exceeding the memory limit due to the above reasons.