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 hai 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 ba 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

Gồm ~q~ dòng trả lời tương ứng cho ~q~ câu hỏi của thầy giáo.

Scoring

Sample Input 1

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

Sample Output 1

YES
YES
NO

Notes

Với trường hợp ~l=2,r=5~, dãy con ~\{8;3;17;18\}~, tổng các ước của ~8~ là ~1+2+4+8=15~, tổng các ước của ~3~ là ~1+3=4~, tổng các ước của ~17~ là ~1+17=18~, tổng các ước của ~18~ là ~1+2+3+6+9+18=39~. Có ~3~ số đặc biệt là ~8;17;18~ vì mỗi số đều có tổng các ước chia hết cho ~3~, với ~k=3~ nên kết quả là "YES".