Canuc rất thích sưu tầm nhạc, đến nay kho nhạc đã chứa rất nhiều album. Các album được đánh số theo dãy số tự nhiên khác 0, các bài nhạc trong album sẽ được đánh số theo số thứ tự của album.

Nhiều lúc ngẫu hứng, Canuc không muốn nghe theo từng album nữa, mà bật chế độ trộn bài để nghe. Chế độ trộn bài sẽ lấy ngẫu nhiên \(n\) bài nhạc bất kì trong kho nhạc để phát.

Tuy nhiên có nhiều bài nhạc trong danh sách trộn Canuc không thích, nên sẽ thay thế một bài ở album khác vào để nghe.

Input

• Hai số tự nhiên \(n, q\) \((1 \leq n, q \leq 3\cdot 10^5)\) với \(n\) là số bài hát trong danh sách trộn bài, \(q\) là số truy vấn.
• Dòng tiếp theo chứa \(n\) số tự nhiên \(a_1, a_2, a_3,...a_n\) \((1 \leq a_i \leq 10^9)\) là thứ tự phát của danh sách sau khi trộn bài. Bài thứ \(i\) là của album \(a_i\).
• \(q\) dòng tiếp theo, mỗi dòng chứa một truy vấn. Có 2 dạng truy vấn:
  • \(1\) \(i\) \(x\) \((1 \leq i \leq n, 1 \leq x \leq 10^9)\)
  • \(2\) \(l\) \(r\) \(k\) \((1 \leq l \leq r \leq n, 1 \leq k \leq n)\)
• Ở truy vấn thứ nhất, Canuc thay bài nhạc thứ \(i\) bởi một bài hát trong album \(x\)
• Ở truy vấn thứ hai, Canuc muốn biết từ bài \(a_l, a_{l+1},...a_r\) số lượng bài nhạc trong từng album xuất hiện trong dãy có chia hết cho \(k\) hay không

Output

• Ở từng truy vấn thứ hai, in ra YES nếu câu trả lời là có, NO nếu không, mỗi câu trả lời trên một dòng

Example

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

YES
YES
YES
NO