This is an interactive problem.

We need to process a class of expressions: each consists of $n$ elements and $n-1$ operators, with exactly one operator between any two adjacent elements, and no parentheses in the expression. For example, $a + b \times c$ is such an expression.

There are $k$ types of these operators, each with a different priority. For convenience, we use integers from $1$ to $k$ to represent these operators, where a larger number indicates a higher priority.

These operators satisfy the commutative and associative laws, i.e., for any elements $a, b, c$ and operator $\sim$, the following hold: $$a \sim b = b \sim a$$ $$a \sim (b \sim c) = (a \sim b) \sim c$$

We denote the initial expression as version $0$.

There are $m$ operations, each of which is one of the following: 1. Element modification: For a certain version, modify the element at a specific position. 2. Operator modification: For a certain version, modify the operator between two specific elements. 3. Reversal: For a certain version, reverse all elements and operators between the $l$-th element and the $r$-th element (inclusive of the $l$-th and $r$-th elements).

We denote the expression obtained after the $i$-th operation as version $i$.

After each operation, you are required to find the value of the current expression.

You can only obtain the result of $a \sim b$ by calling a function $F(a, b, op)$, and there is a limit on the number of times this function can be called.

Implementation Details

You must submit a single source file expr.cpp/c/pas implementing the required functions.

For C/C++ language users: You need to include the header file expr.h. The definition of the Data type is:

typedef struct {
    int x;
} Data;

Functions you need to implement:

void init(int test_id, int n, int m, int k, const Data *a, const int *ops);
Data modify_data(int id, int pos, Data x);
Data modify_op(int id, int pos, int new_op);
Data reverse(int id, int l, int r);

The interface for function $F$ is:

Data F(Data a, Data b, int op);

For Pascal language users: You need to use the unit graderhelperlib. The definition of the Data type is:

type Data = record
    x : longint;
end;

Functions you need to implement:

procedure init(test_id, n, m, k : longint; const a : array of Data; const ops : array of longint);
function modify_data(id, pos : longint; x : Data) : Data;
function modify_op(id, pos, new_op : longint) : Data;
function reverse(id, l, r : longint) : Data;

The interface for function $F$ is:

function F(a, b : Data; op : longint) : Data;

Note: ops[0] is meaningless; please do not attempt to access it. The variable x in the Data type is only meaningful to the interaction library; you do not need to, and should not, access this variable. Ensure that the $a, b$ passed to function $F$ and the return values of the three operation functions are elements provided by init, modify_data, or F.

Data Constraints

Scoring

If the program terminates normally, the correctness will be checked. If the answer is incorrect, or the number of calls to function $F$ exceeds the limit for the test case, the test case will be scored as 0 points. Otherwise, it will be awarded full points.

Examples

Input 1

0 5 5 2
1000
2 1 1 1
0 1 1
1 2 2 2
2 3 1 3
0 3 0 3
0 3 1 1

Output 1

120400404

Note

This is the checksum of the output obtained using the grader and the correct source code. If your program produces a different checksum, it is incorrect for this sample. Using $+$ and $\times$ to represent the two operators, and lowercase letters for elements, the expressions for each version are: - Version 0: $a \times b + c + d + e$ - Version 1: $a \times f + c + d + e$ - Version 2: $a \times f \times c + d + e$ - Version 3: $a \times d + c \times f + e$ - Version 4: $d + c + a \times f + e$ - Version 5: $a \times b + c + d + e$

Input 2

(See expr/expr.in in the contestant directory)

Output 2

(See expr/expr.ans in the contestant directory)