题目描述

给出一个长度为 $n$ 的非负整数序列 $a_1,a_2,a_3,\ldots, a_n$，给出 $q$ 次操作，每次先给出一个参数 $op$：

• $op=0$，接下来给出 $2$ 个参数 $x,y$，把 $a_x$ 修改为 $y$。

• $op=1$，接下来给出 $4$ 个参数 $l_1,r_1,l_2,r_2$（保证 $r_1-l_1=r_2-l_2$），你需要判断区间 $[l_1,r_1]$ 与区间 $[l_2,r_2]$ 是否本质相同，如果本质相同输出 YES，否则输出 NO。

本质相同的定义：令区间长度为 $\text{len}$ ，序列 $p_{1}\dots p_{\text{len}}$ 为 $a_{l_1}\dots a_{r_1}$ 升序排序后的结果，序列 $q_{1}\dots q_\text{len}$ 为 $a_{l_2}\dots a_{r_2}$ 升序排序后的结果，存在一个整数 $k$ 使得满足 $\forall i,p_i+k=q_i$。

输入格式

第一行给出两个正整数 $n,q$，表示序列长度及操作次数。

第二行 $n$ 个非负整数表示 $a_{1},a_2,a_3,\ldots,a_n$。

接下来 $q$ 行，每行为上述操作中的一种。

输出格式

对于 $op=1$ 的操作，输出两个区间是否本质相同，如果是输出 YES，否则输出 NO。

12 6
1 1 4 5 1 4 2 2 5 2 3 3
1 1 3 7 9
1 2 3 5 6
1 1 3 2 4
0 7 1
1 1 4 2 5
1 5 7 8 10

YES
YES
NO
YES
YES

提示

• Subtask1 （$25$ pts）：$1\leq n,q \leq 1000$。

• Subtask2 （$25$ pts）：$1\leq n,q \leq 10^5$，$0\leq a_i,y\leq 100$。

• Subtask3 （$25$ pts）：$1\leq n,q \leq 10^5$。

• Subtask4 （$25$ pts）：无特殊限制。

你只有通过 subtask 中的所有测试点才能获得该 subtask 的分数。

对于所有数据满足：$1\leq n,q \leq 10^6$，$1\leq x \leq n$，$0\leq a_i,y \leq 10^6$ 。且对于所有 $l,r$ 有 $1\leq l\leq r\leq n$。