正如前面提到的,威廉非常喜欢玩电子游戏。在他最喜欢的游戏之一中,玩家角色身处一个宇宙中,其中每个行星都由从 $$$0$$$ 到 $$$2^n - 1$$$ 的二进制数指定。在每个星球上,如果 $$$i$$$ 和 $$$j$$$ 的二进制表示恰好有一位不同,则允许玩家从星球 $$$i$$$ 移动到星球 $$$j$$$ 。
William 想测试你,看看你如何处理这个游戏世界中的以下查询:
- 摧毁编号从 $$$l$$$ 到 $$$r$$$(含)的行星。这些行星不能再被移动到了。
- 找出是否有可能使用一定数量的行星门从 $$$a$$$ 行星到达 $$$b$$$ 行星。保证行星 $$$a$$$ 和 $$$b$$$ 不会被摧毁。
输入
第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 50$$$, $$$1 \leq m \leq 5 \cdot 10^4$$$),分别是每个行星名称的二进制表示的位数和查询的数量。
接下来的 $$$m$$$ 行包含两种类型的查询:
block l r — 查询编号从 $$$l$$$ 到 $$$r$$$ 的行星毁灭情况($$$0 \le l \le r < 2^n$$$)。保证没有一个星球会被毁灭两次。
询问 a b — 查询行星 $$$a$$$ 和 $$$b$$$ 之间的可达性 ($$$0 \le a, b < 2^n$$$)。可以保证行星 $$$a$$$ 和 $$$b$$$ 尚未被摧毁。
输出
对于询问类型的每个查询,如果可以从行星 $$$a$$$ 到达行星 $$$b$$$,则必须在新行中输出“1”,否则输出“0”(不带引号)。
示例
输入 #1
3 3 ask 0 7 block 3 6 ask 0 7
输出 #1
1 0
输入 #2
6 10 block 12 26 ask 44 63 block 32 46 ask 1 54 block 27 30 ask 10 31 ask 11 31 ask 49 31 block 31 31 ask 2 51
输出 #2
1 1 0 0 1 0
注意
第一个示例测试可以通过以下方式可视化:
对查询询问 0 7 的响应是肯定的。
接下来,在查询块 3 6 之后,图形将如下所示(被破坏的顶点突出显示):
对查询 Ask 0 7 的响应是否定的,因为从顶点 $$$0$$$ 到顶点 $$$7$$$ 的任何路径都必须经过被破坏的顶点之一。