Distinct Values Queries II

Source: CSES

Version: Phuoc Hung OJ Extended

Problem

Process point updates 1 k u and queries 2 a b asking whether all values in subarray $[a,b]$ are pairwise distinct.

Input

The first line contains $n,q$, then the initial array, followed by $q$ operations.

Output

For every type-2 query print YES if all values are distinct, otherwise NO.

Subtasks

Subtask 1 (20%)

• $n\le 30$, number of queries $\le 30$.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, number of queries $\le 3000$.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le2\cdot10^5$
• $1\le x_i,u\le10^9$
• $1\le k\le n$
• $1\le a\le b\le n$

Example

Input

5 4
3 2 7 2 8
2 3 5
2 2 5
1 2 9
2 2 5

Output

YES
NO
YES

Explanation

Initially [2,5] contains [2,7,2,8], so it is not distinct. After changing position 2 to 9, the same range becomes [9,7,2,8].