题目描述

Lazo 梦想着成为一名酒吧调酒师。为了训练自己，他正在练习调制鸡尾酒。

Lazo 的迷你吧台里有 10^5 种不同的饮料，方便起见编号为 1 到 10^5。他还摆放了 N 个空杯子，按顺序编号为 1 到 N。在本题中可以认为每个杯子的容量都是无限的。

训练一共进行 Q 步。每一步恰好发生以下两种事件之一：

1. 选择一种饮料 X_i，向所有编号在 [L_i, R_i] 内的杯子各倒入恰好 1 盎司该饮料；
2. 询问所有编号在 [L_i, R_i] 内的杯子，是否都含有完全相同的混合物。

这里认为两个杯子中的混合物相同，当且仅当它们对每一种饮料都含有完全相同的数量。倒入顺序不影响结果。

对于第一类操作，Lazo 很容易完成；但第二类问题难倒了他。请你编写程序 cocktails，回答所有第二类询问。

注：1 盎司约等于 30 毫升。

输入格式

第一行输入两个整数 N, Q，分别表示杯子数和操作数。
接下来 Q 行，每行描述一个操作，格式为以下两种之一：

• 1 L_i R_i X_i：向所有编号在 [L_i, R_i] 内的杯子各加入 1 盎司饮料 X_i；
• 2 L_i R_i：询问区间 [L_i, R_i] 内所有杯子是否都含有相同混合物。

输出格式

对于每个类型 2 的询问，输出一行：

• 1 表示是；
• 0 表示否。

数据范围

1 <= N, Q <= 2 × 10^5
1 <= X_i <= 10^5
1 <= L_i <= R_i <= N

子任务

样例 1

输入 1

4 7
2 1 3
1 1 3 5
1 3 4 6
2 1 3
2 1 2
1 2 2 5
2 1 2

输出 1

1
0
1
0

样例解释 1

按顺序考虑每一步：

• 2 1 3：询问杯子 1, 2, 3 是否相同。三者都为空，因此答案为 1；
• 1 1 3 5：向杯子 1, 2, 3 各加入 1 盎司饮料 5；
• 1 3 4 6：向杯子 3, 4 各加入 1 盎司饮料 6；
• 2 1 3：此时杯子 1 和 2 各只有 1 盎司饮料 5，而杯子 3 还有 1 盎司饮料 6，所以答案为 0；
• 2 1 2：杯子 1 和 2 都只有 1 盎司饮料 5，所以答案为 1；
• 1 2 2 5：向杯子 2 再加入 1 盎司饮料 5，于是其中共有 2 盎司饮料 5；
• 2 1 2：杯子 1 含 1 盎司饮料 5，杯子 2 含 2 盎司饮料 5，所以答案为 0。