Nhân dịp Halloween, Tí mở một lễ hội trưng bày bí ngô. Ban đầu quầy trưng bày không có quả nào cả và lễ hội được diễn ra trong ~q~ ngày. Vào ngày thứ ~i~, sẽ có một trong hai hoạt động sau:

• Hoạt động ~1~ có dạng ~1~ ~w~ ~v~ ~e~: Tí sẽ mua thêm một quả bí ngô có khối lượng là ~w~, độ đẹp là ~v~. Tuy nhiên, quả bí ngô này sẽ bị hỏng sau ngày thứ ~e~ và Tí sẽ loại bỏ nó khỏi quầy hàng của mình.
• Hoạt động ~2~ có dạng ~2~ ~w~: Tèo thách Tí sử dụng những quả bí ngô có sẵn của mình để trưng bày sao cho tổng khối lượng của các quả bí ngô đúng bằng ~w~ và có độ đẹp là lớn nhất. Lưu ý: độ đẹp của các quả bí ngô được trưng bày là tổng độ đẹp của các quả, một tập rỗng có thể tích và khối lượng bằng ~0~.

Dữ liệu

Nhập từ file pumpkin_festival.inp:

• Dòng đầu tiên chứa ~3~ số nguyên ~q~, ~maxW~, ~T~ lần lượt là số lượng ngày của lễ hội, khối lượng tối đa của các quả bí ngô.
• ~q~ dòng tiếp theo, mỗi dòng mô tả một hoạt động trong ngày. Số nguyên ~type~ ~(type \in \{1,2\})~ cho biết loại hoạt động. Tiếp đó, là ~3~ hoặc ~1~ số nguyên đã được mã hóa. Để giải mã, gọi ~D = T \times lastAns~, số ~x~ sẽ được thay bằng ~x - D~. Ở đây ~lastAns = a \oplus b~ với ~a~,~b~ là kết quả của hoạt động loại ~2~ trước đó, ~\oplus~ là phép ~XOR~. Ban đầu ~lastAns = 0~ nếu chưa có hoạt động loại ~2~ nào.

Kết quả

Xuất ra file pumpkin_festival.out:

• Với mỗi hoạt động loại ~2~, in ra hai số nguyên ~a~ và ~b~ trên cùng một dòng, cách nhau bởi một dấu cách. Trong đó, ~a = 1~ nếu Tí có thể sử dụng những quả bí ngô có sẵn của mình để trưng bày sao cho tổng khối lượng của các quả bí ngô đúng bằng ~w~, ngược lại ~a = 0~ và ~b~ là tổng đẹp lớn nhất của những quả bí ngô đó, ~b = 0~ nếu ~a = 0~.

Giới hạn

• ~1 \le q \le 15000~
• ~1 \le w_i \le maxW \le 15000~
• ~1 \le v_i \le 15000~
• ~i \le e_i \le q~

Ràng buộc

• Subtask ~1 \ (5 \ \text{test}): q \le 18, v \le 15000, T = 0~
• Subtask ~2 \ (7 \ \text{test}): q,v \le 1000, T \in \{0,1\}~
• Subtask ~3 \ (7 \ \text{test}): q,v \le 6000, T = 0~
• Subtask ~4 \ (7 \ \text{test}): q,v \le 10000, T = 0~
• Subtask ~5 \ (7 \ \text{test}):~ Không có ràng buộc gì thêm

Ví dụ 1

Dữ liệu

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

Kết quả

1 0
1 7
0 0

Ví dụ 2

Dữ liệu

6 10 1
1 1 1 6
1 4 0 5
2 4
1 4 8 7
2 8
2 13

Kết quả

1 0
1 7
0 0