「Wdsr-2.5」未来水妖集市
题目背景
每年,河城荷取(河童)都要为未来水妖集市准备展品,以及用于销售的商品。于是河童会生产大批量的产品。
为了提高生产效率,河童决定搭建一条生产线。具体而言,河童会利用她的机械臂,构建出一长串的机器。每个机器只会对原材料进行若干次加工,最终输出成品。
由于河童需要调试设备,于是机械臂每次操作后,河童会用一些询问确定这条生产线目前的性能如何。为了顺利完成生产任务,河童找到了你,希望你写一个程序告诉她每次操作后生产线的性能。
题目描述
初始时原材料会有一个初始权值 。然后它会经过若干个机器的加工,花费若干点**加工指数**,得到最终产品。
河童的机器有两种:
- 0 型:每次加工花费 $v_i$ 的加工指数,让材料的附加值增加 $w_i$ 。材料经过时**最多只能加工一次**。
- 1 型:每次加工花费 $v_i$ 的加工指数,让材料的附加值增加 $w_i$ 。材料经过时**加工次数无限制**。
现在河童会利用一个机械臂来设计这套工艺流程。初始时,流水线上没有一台机器,机械臂放在位置 $0$。机器的位置编号是从 $1$ 开始的。现在河童会告诉你加工指数的最大值 $v$ ,然后她会下达 $q$ 个命令。不妨设每个指令执行前,机械臂的位置在 $p$ 。
每个指令的格式为 $\colorbox{#f0f0f0}\verb!opt ti vi wi xi yi!$ ,其中 $opt$ 表示操作的种类。共有如下几种:
1. **右移**:将机械臂向右移动一格,即 $p\gets p+1$。
2. **左移**:将机械臂向左移动一格,即 $p\gets p-1$。
3. **插入机器**:在机械臂当前位置插入一个机器,它的类型为 $t_i$ ,每次消耗的加工指数为 $v_i$ ,材料的附加值会增加 $w_i$ ,插入的机器的位置为 $p+1$ 。机械臂位置不变,但是被插入的机器右侧的机器都会向右移动一格。
4. **删除机器**:在机械臂当前位置移除一个机器,移除的机器位置为 $p+1$ 。移除机器后机械臂位置不变,但是被移除的机器右侧的机器都会向左移动一格。
5. **修改机器**:在机械臂当前位置修改一个机器的参数。即修改的机器的位置为 $p+1$ 。
对于操作 1, 2, 4,请忽略参数 $\colorbox{#f0f0f0}\verb!ti vi wi!$ 。
每次操作完,河童会询问你,如果一个初始权值为 $x_i$ 的物品从左侧起第一个机器进去,直到从右边机器出来,依次加工,消耗最多 $y_i$ 点加工点数( $y_i\le v$ ),这个物品可以获得的最大权值。特别地,如果此时没有一台机器,此物品权值不变。
假设某一时刻共有 $u$ 台机器,那么数据保证在此时刻机械臂的位置必然在 $[0,u]$ 内。
输入输出格式
输入格式
第一行两个正整数 $q,v$ ,含义如题面所述。
接下来 $q$ 行,每行 $6$ 个正整数 $opt',t_i',v_i',w_i',x_i',y_i'$ 。你需要**将它们分别异或上** $\boldsymbol{last}$ 来获得真实的 $opt,t_i,v_i,w_i,x_i,y_i$ 。其中 $last$ 为上次输出的结果。特别地,初始时 $last=0$ 。
输出格式
输出共 $q$ 行,每行一个正整数,表示每次询问的答案。
输入输出样例
输入样例 #1
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
输出样例 #1
1005
1005
1020
1008
1005
1005
说明
#### 样例 1 说明
解码后的输入数据:
```plain
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
```
#### 样例 2, 3
见下发附件。
#### 数据规模与约定
- 对于 $10\%$ 的数据,满足 $q,v\le 10$ 。
- 对于另外 $20\%$ 的数据,满足 $v\le 100$ 。
- 对于另外 $20\%$ 的数据,满足 $q,v\le 2\times 10^3$ 。
- 对于 $100\%$ 的数据, 满足 $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$ 。