Cho một dãy số nguyên ~a_1, a_2, \cdots, a_n~ gồm ~n~ phần tử và một số nguyên ~m~. Bạn cần xử lý ~q~ truy vấn, trong đó mỗi truy vấn thuộc một trong hai loại sau:

• ~1~ ~l~ ~r~ ~val~: với mỗi chỉ số ~i~ thoả mãn ~l \le i \le r~, thực hiện gán ~a_i = (a_i + val) \mod m~.

• ~2~ ~l~ ~r~: kiểm tra xem trong đoạn con ~a_l, a_{l + 1}, \cdots, a_r~ có tồn tại ít nhất hai giá trị khác nhau hay không.

Với từng truy vấn loại ~2~, nếu có, in ra ~\text{YES}~, ngược lại in ra ~\text{NO}~ nếu tất cả các phần tử trong đoạn đều bằng nhau.

Input

Dòng đầu chứa ba số nguyên ~n, q~ và ~m~ (~1 \le n, q \le 2 \times 10^5~, ~m \le 10^9~);

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \cdots, a_n~ (~0 \le a_i < m~);

Trong ~q~ dòng cuối cùng, mỗi dòng mô tả một truy vấn thuộc một trong hai loại trên (~1 \le l \le r \le n~, ~0 \le val < m~).

Output

Với mỗi truy vấn loại 2, in ra trên một dòng chứa kết quả tương ứng là ~\text{YES}~ hoặc ~\text{NO}~.

Scoring

Sample Input 1

5 5 10
1 2 3 4 5
2 1 3
1 2 4 8
2 1 3
1 2 3 1
2 1 2

Sample Output 1

YES
YES
NO

Notes

Truy vấn 1 tồn tại hai giá trị khác nhau (1, 3) : 1 và 2

Sau truy vấn 2, dãy thay đổi thành [1, 0, 1, 2, 5]

Sau truy vấn 4, dãy thay đổi thành [1, 1, 2, 2, 5]

Truy vấn cuối cùng (1,2) không có hai giá trị nào khác nhau