Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

F. Kazaee
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have an array a consisting of n positive integers and you have to handle q queries of the following types:

  • 1 i x: change ai to x,
  • 2 l r k: check if the number of occurrences of every positive integer in the subarray al,al+1,ar is a multiple of k (check the example for better understanding).
Input

The first line of the input contains two integers n and q (1n,q3105), the length of a and the number of queries.

Next line contains n integers a1,a2,an (1ai109) — the elements of a.

Each of the next q lines describes a query. It has one of the following forms.

  • 1 i x, (1in , 1x109), or
  • 2 l r k, (1lrn , 1kn).
Output

For each query of the second type, if answer of the query is yes, print "YES", otherwise print "NO".

Example
Input
10 8
1234 2 3 3 2 1 1 2 3 4
2 1 6 2
1 1 1
2 1 6 2
2 1 9 2
1 10 5
2 1 9 3
1 3 5
2 3 10 2
Output
NO
YES
NO
YES
YES
Note

In the first query, requested subarray is [1234,2,3,3,2,1], and it's obvious that the number of occurrence of 1 isn't divisible by k=2. So the answer is "NO".

In the third query, requested subarray is [1,2,3,3,2,1], and it can be seen that the number of occurrence of every integer in this sub array is divisible by k=2. So the answer is "YES".

In the sixth query, requested subarray is [1,2,3,3,2,1,1,2,3], and it can be seen that the number of occurrence of every integer in this sub array is divisible by k=3. So the answer is "YES".