Description

Initially, the raw material has an initial value. Then it will be processed by several machines, spending some processing index, to obtain the final product.

Nitori's machines come in two types:

• Type 0: Each processing costs $v_i$ processing index, and increases the material's added value by $w_i$. When the material passes through, it can be processed at most once.
• Type 1: Each processing costs $v_i$ processing index, and increases the material's added value by $w_i$. When the material passes through, the number of processings is unlimited.

Now Nitori uses a robotic arm to design this process flow. Initially, there is no machine on the line, and the robotic arm is at position $0$. Machine positions are numbered starting from $1$. Now Nitori tells you the maximum processing index $v$, and then she issues $q$ commands. Suppose that before executing each command, the robotic arm is at position $p$.

Each command has the form $\colorbox{#f0f0f0}\verb!opt ti vi wi xi yi!$, where $opt$ indicates the type of operation. There are the following types:

1. Move right: Move the robotic arm one step to the right, i.e. $p\gets p+1$.
2. Move left: Move the robotic arm one step to the left, i.e. $p\gets p-1$.
3. Insert machine: Insert a machine at the current position of the robotic arm. Its type is $t_i$, the processing index cost per processing is $v_i$, and the material's added value increases by $w_i$. The inserted machine's position is $p+1$. The robotic arm position does not change, but all machines to the right of the inserted machine shift one position to the right.
4. Delete machine: Remove a machine at the current position of the robotic arm. The removed machine is at position $p+1$. After removal, the robotic arm position does not change, but all machines to the right of the removed machine shift one position to the left.
5. Modify machine: Modify a machine's parameters at the current position of the robotic arm, i.e. modify the machine at position $p+1$.

For operations 1, 2, and 4, please ignore the parameters $\colorbox{#f0f0f0}\verb!ti vi wi!$.

After each operation, Nitori asks you: for an item with initial value $x_i$, entering from the leftmost (first) machine and exiting from the rightmost machine, being processed in order, spending at most $y_i$ processing points ($y_i\le v$), what is the maximum value the item can obtain. In particular, if there is no machine at this time, the item's value does not change.

Suppose at some moment there are $u$ machines in total. The data guarantees that at this moment, the robotic arm position must be within $[0,u]$.

Input Format

The first line contains two positive integers $q,v$, with meanings as described above.

In the next $q$ lines, each line contains $6$ positive integers $opt',t_i',v_i',w_i',x_i',y_i'$. You need to XOR each of them with $\boldsymbol{last}$ to obtain the real $opt,t_i,v_i,w_i,x_i,y_i$. Here $last$ is the previous output result. In particular, initially $last=0$.

Output Format

Output $q$ lines in total, each line containing one positive integer, representing the answer to the query after each operation.

6 10
3 0 4 5 1000 7
1004 1005 1004 1004 5 997
1006 1004 1000 999 5 999
1017 1021 1023 1023 20 1019
1012 1009 1009 1009 24 1018
1007 1004 1004 1004 5 997

1005
1005
1020
1008
1005
1005

Hint

Sample 1 Explanation

Decoded input data:

6 10
3 0 4 5 1000 7
1 0 1 1 1000 8
3 1 5 10 1000 10
5 1 3 3 1000 7
4 1 1 1 1000 10
2 1 1 1 1000 8

Samples 2 and 3

See the attached files provided.

Constraints

• For $10\%$ of the testdata, $q,v\le 10$.
• For another $20\%$ of the testdata, $v\le 100$.
• For another $20\%$ of the testdata, $q,v\le 2\times 10^3$.
• For $100\%$ of the testdata, $1\le q\le 3\times 10^4;1\le v\le 2\times 10^4;1\le x_i,y_i,w_i\le 4\times 10^4$.

Translated by ChatGPT 5