整数

题目背景

在人类智慧的山巅,有着一台字长为 1048576 位的超级计算机,著名理论计算机科 学家 P 博士正用它进行各种研究。不幸的是,这天台风切断了电力系统,超级计算机 无法工作,而 P 博士明天就要交实验结果了,只好求助于学过 OI 的你......

问题描述

P 博士将他的计算任务抽象为对一个整数的操作。
具体来说,有一个整数 x ,一开始为 0。 接下来有 n 个操作,每个操作都是以下两种类型中的一种:
• 1 a b :将 x 加上整数 a·2b,其中 a 为一个整数,b 为一个非负整数
• 2 k :询问 x 在用二进制表示时,位权为 2k 的位的值(即这一位上的 1 代表 2k )
保证在任何时候,x≥0。

输入格式

从标准输入读入数据。输入的第一行包含四个正整数 n,t1,t2,t3,n 的含义见题目描述,t1,t2,t3 的具体含义 见子任务。  接下来 n 行,每行给出一个操作,具体格式和含义见题目描述。 同一行输入的相邻两个元素之间,用恰好一个空格隔开。

输出格式

输出到标准输出。
对于每个询问操作,输出一行,表示该询问的答案(000 或 111)。 对于加法操作,没有任何输出。

样例

输入样例

10 3 1 2
1 100 0
1 2333 0
1 -233 0
2 5
2 7
2 15
1 5 15
2 15
1 -1 12
2 15

Output

0
1
0
1
0

样例解释

子任务

【子任务】 内存限制512M,每个测试点2秒。在所有测试点中,
1 ≤ t1 ≤ 3,1 ≤ t2 ≤ 4,1 ≤ t3 ≤ 2。
不同的 t1,t2,t3 对应的特殊限制 如下:
• 对于 t1 = 1 的测试点,满足 a = 1
•对于 t1 = 2 的测试点,满足 |a|= 1
• 对于 t1 = 3 的测试点,满足 |a|≤109 • 对于 t2 = 1 的测试点,满足 0≤b,k≤30
• 对于 t2 = 2 的测试点,满足 0≤b,k≤100
• 对于 t2 = 3 的测试点,满足 0≤b,k≤n
• 对于 t2 = 4 的测试点,满足 0≤b,k≤30n
• 对于 t3 = 1 的测试点,保证所有询问操作都在所有修改操作之后
• 对于 t3 = 2 的测试点,不保证询问操作和修改操作的先后顺序

信息

难度
9
分类
(无)
标签
递交数
2
已通过
1
通过率
50%
上传者