n 个柜子，每个柜子里都摆放了一个物品，第 i 个柜子里的物品编号为 a_i。

请维护物品放置信息，以实现下面的两个操作：

• 1 x，取走第 x 个柜子里的物品，保证此时这个柜子里的物品还在。
• 2 l r，询问第 l 到第 r 个柜子未被取走的物品中是否有两个物品编号相同。

第一行以空格分隔的两个正整数 n,q \ (1 \leq n,q \leq 5 \times 10^5)。

接下来一行 n 个正整数 a_i \ (1 \leq a_i \leq 10^6)。

接下来 q 行每行一个操作，格式见题目描述。数据保证 1\leq x,l \leq r \leq n。

对于每个询问，输出一行一个整数，如果在指定的区间内有两个物品编号相同则输出 1，否则输出 0。