CF1556G.Gates to Another World

As mentioned previously William really likes playing video games. In one of his favorite games, the player character is in a universe where every planet is designated by a binary number from $0$ to $2^n - 1$. On each planet, there are gates that allow the player to move from planet $i$ to planet $j$ if the binary representations of $i$ and $j$ differ in exactly one bit.

William wants to test you and see how you can handle processing the following queries in this game universe:

• Destroy planets with numbers from $l$ to $r$ inclusively. These planets cannot be moved to anymore.
• Figure out if it is possible to reach planet $b$ from planet $a$ using some number of planetary gates. It is guaranteed that the planets $a$ and $b$ are not destroyed.

如前所述，威廉非常喜欢玩电子游戏。在他最喜爱的一款游戏中，玩家角色所处的宇宙中，每颗行星均用一个从 $0$ 到 $2^n - 1$ 的二进制数标识。在每颗行星上，都设有传送门，允许玩家从行星 $i$ 移动到行星 $j$，当且仅当 $i$ 与 $j$ 的二进制表示恰好有一位不同。

威廉想考验你，看你能否在这个游戏宇宙中高效处理以下两类查询：

• 摧毁编号在区间 $[l, r]$ 内（含端点）的所有行星。这些被摧毁的行星将不再可到达。
• 判断是否能通过若干次行星传送门，从行星 $a$ 到达行星 $b$。题目保证行星 $a$ 和 $b$ 均未被摧毁。

The first line contains two integers $n$, $m$ ($1 \leq n \leq 50$, $1 \leq m \leq 5 \cdot 10^4$), which are the number of bits in binary representation of each planets' designation and the number of queries, respectively.

Each of the next $m$ lines contains a query of two types:

block l r — query for destruction of planets with numbers from $l$ to $r$ inclusively ($0 \le l \le r \lt 2^n$). It's guaranteed that no planet will be destroyed twice.

ask a b — query for reachability between planets $a$ and $b$ ($0 \le a, b \lt 2^n$). It's guaranteed that planets $a$ and $b$ hasn't been destroyed yet.

第一行包含两个整数 $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 \lt 2^n$）。保证任意行星不会被摧毁两次。

ask a b — 查询行星 $a$ 与行星 $b$ 之间是否可达（$0 \le a, b \lt 2^n$）。保证行星 $a$ 和 $b$ 尚未被摧毁。

For each query of type ask you must output "1" in a new line, if it is possible to reach planet $b$ from planet $a$ and "0" otherwise (without quotation marks).

对于每个类型为 ask 的查询，如果可以从星球 $a$ 到达星球 $b$，则在新的一行输出 1，否则输出 0（不带引号）。

The first example test can be visualized in the following way:

Response to a query ask 0 7 is positive.

Next after query block 3 6 the graph will look the following way (destroyed vertices are highlighted):

Response to a query ask 0 7 is negative, since any path from vertex $0$ to vertex $7$ must go through one of the destroyed vertices.

第一个示例测试可可视化为如下所示：

对查询 ask 0 7 的回答为“是”。

在执行查询块 3 6 后，图将变为如下所示（被摧毁的顶点已高亮显示）：

此时对查询 ask 0 7 的回答为“否”，因为从顶点 $0$ 到顶点 $7$ 的任意路径都必须经过至少一个被摧毁的顶点。