题目描述

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

Alice 和 Karen 家边的大花坛给了她们无尽的欢乐。

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

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

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

输入格式

第一行三个正整数 $q,\text{maxv},T$ 表示操作数、最大可能的 $v$、及是否强制在线。

接下来 $q$ 行每行描述一个操作。
设修正值 $d=T\times \text{lastans}$。这里 $\text{lastans}$ 表示上次询问的两个答案的异或和，若没有上次询问则 $\text{lastans}=0$。
则第 $i$ 行中，第一个整数 $\text{op}$ 表示操作类型；
若操作类型为 $1$，则接下来三个整数 $v',w',e'$ 表示加入一个体积为 $v_i=v'-d$，价值为 $w_i=w'-d$，在第 $e_i=e'-d$ 时间后被移除的物品；
若操作类型为 $2$，则接下来一个整数 $v'$ 表示询问 $v_i=v'-d$。
一行中相邻整数以单个空格分隔。

输出格式

对于每个询问（$2$ 类型的操作）输出一行两个整数 $e$ 和 $\text{maxw}$，由空格分隔。

若不存在这样的子集，$e=\text{maxw}=0$；
否则 $e=1$，$\text{maxw}$ 为最大的价值和。

样例 1

input

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

output

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

样例 2

input

19 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

output

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

数据范围与提示

对于所有数据，$1\le q\le 15000,1\le v_i\le \text{maxv}\le 15000,0\le w_i\le 15000,i\le e_i\le q$。

对于每个测试点，若问题 1 回答全对，则得 $40\%$ 的分数；若问题 2 回答全对，则另得 $60\%$ 的分数。每个子任务的得分是其中各测试点的最小值。
注意，即使你只回答了一个问题，每次仍要输出两个整数，以免答案错位。