1015: 花团

「Alice —— !」「Karen —— !」 

Alice 和 Karen 家边的大花坛给了她们无尽的欢乐。
这天 Karen 想重新规划一下花坛在一年里的外观。但是由于花朵各有其花期，而且花市上的选择实在太多了，所以她把问题进行了一些抽象，希望擅长程序设计的你可以为她解决。

物品集合 S 初始为空，按时间递增顺序依次给出  q 次操作，操作如下：

• 1 v w e 表示在 S 中加入一个体积为 v 价值为 w 的物品，第 e 次操作结束之后移除该物品。
• 2 v 表示询问。你需要回答：
  1. 当前 S 是否存在一个子集使得子集中物品体积和为 v。
  2. 当前 S 的所有物品体积和为 v 的子集中，价值和最大是多少（空集的价值和为 0）

第一行三个正整数 q,maxv,T 表示操作数、最大可能的 v、及是否强制在线。
接下来 q 行每行描述一个操作。
设修正值 d=T*lastans。这里 lastans 表示上次询问的两个答案的异或和，若没有上次询问则 lastans=0。
则第 i 行中，第一个整数op 表示操作类型；
若操作类型为 1，则接下来三个整数 v',w',e' 表示加入一个体积为 v_i=v'-d，价值为 w_i=w'-d，在第 e_i=e'-d 时间后被移除的物品；
若操作类型为 2，则接下来一个整数 v' 表示询问 v_i=v'-d。
一行中相邻整数以单个空格分隔。
对于所有数据，1<=q<=15000,1<= v_i<=maxv<=15000,0<=wi<=5000,i<=e_i<=q。

对于每个询问（2 类型的操作）输出一行两个整数 e 和 maxw，由空格分隔。
若不存在这样的子集，e=maxw=0；
否则 e=1，maxw 为最大的价值和。

12 10 0
1 1 1 12
1 6 0 12
1 10 7 8
1 3 8 7
2 6
2 9
2 10
2 10
2 10
1 3 2 11
2 4
2 4

1 0
1 8
1 9
1 7
0 0
1 3
0 0

输入2：

9 20 1
1 2 19 11
2 2
1 27 27 22
1 20 34 36
2 29
1 9 8 9
1 5 19 8
1 1 15 19
2 3
1 36 40 54
1 37 50 52
2 40
2 62
1 1 17 16
1 1 7 16
1 13 16 18
1 9 11 19
2 10
2 34

输出2：

1 19
0 0
1 34
1 46
0 0
1 26
0 0