Trong buổi học chuyên đề về số học, thầy giáo đưa ra khái niệm số đặc biệt: một số nguyên dương \(x\) gọi là số đặc biệt nếu tổng các ước nguyên dương của \(x\) chia hết cho \(3\).

Ví dụ: \(15\) là một số đặc biệt (vì tổng các ước của \(15\) là \(1 + 3 + 5 + 15 = 24\) chia hết cho \(3\)); \(12\) không phải số đặc biệt (vì tổng các ước của \(12\) là \(1 + 2 + 3 + 4 + 6 + 12 = 28\) không chia hết cho \(3\)).

Cho trước một dãy số có \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\), thầy đưa ra \(q\) câu hỏi có dạng \(l, r, k\) với ý nghĩa số lượng số đặc biệt trong dãy con \(a_l, a_{l+1}, \dots, a_r\) (\(1 \le l \le r \le n\)) có lớn hơn hoặc bằng \(k\) hay không, nếu có thì trả lời YES, ngược lại trả lời NO. Thầy yêu cầu cả lớp lập trình trả lời \(q\) câu hỏi trên.

Yêu cầu: Hãy viết chương trình trả lời \(q\) câu hỏi của thầy giáo.

Input

• Dòng thứ nhất chứa \(2\) số nguyên dương \(n, q\) (\(2 \le n, q \le 10^5\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^5, 1 \le i \le n\)).
• \(q\) dòng tiếp theo mỗi dòng gồm \(3\) số nguyên dương \(l, r, k\) (\(1 \le l \le r \le n, 1 \le k \le 10^5\)).
• Các số trên một dòng cách nhau một khoảng trắng.

Output

• Xuất ra màn hình gồm \(q\) dòng trả lời tương ứng cho \(q\) câu hỏi của thầy giáo.

Example

5 3
19 8 3 17 18
2 5 3
4 4 1
3 3 1

YES
YES
NO

Scoring

• \(50\%\) số điểm tương ứng với số test có: \(n, q \le 10^3\).
• \(50\%\) số điểm tương ứng với số test còn lại không ràng buộc gì thêm.