Mỗi phân số đều có thể biểu diễn được dưới dạng một số thập phân hữu hạn hay vô hạn tuần hoàn, ví dụ $\frac{1}{3}=0,3333...$, $\frac{1}{2}=0,5$, ....

Cho hai dãy số có $n$ phần tử $(a):a_1,...,a_n$ , $(b):b_1,...,b_n$, các số trong dãy là một chữ số khác $0$. Với mỗi truy vấn dạng $ij$, bạn hãy kiểm tra xem phân số $\frac{a_i{a}_{i+1}...a_j}{b_i{b}_{i+1}...b_j}$ là hữu hạn hay vô hạn tuần hoàn.

Ghi chú: Dấu nhân được lược bỏ $(x\ast y=xy)$ để biểu thức ngắn gọn.

Đầu vào

Dòng đầu tiên chứa số tự nhiên $n,q$ $(1\le n,q\le 2\ast {10}^5)$ số phần tử trong dãy và số truy vấn.

Dòng thứ hai chứa $n$ số tự nhiên trong khoảng $[1,9]$, các phần tử của dãy số $(a)$.

Dòng thứ ba chứa $n$ số tự nhiên trong khoảng $[1,9]$, các phần tử của dãy số $(b)$.

$q$ dòng tiếp theo, mỗi dòng chứa hai số tự nhiên $l,r$ $(1\le l\le r\le n)$, một truy vấn.

Đầu ra

Với mỗi truy vấn, xuất ra trên một dòng kí tự $Y$ nếu kết quả là phân số hữu hạn, xuất ra $N$ trong trường hợp còn lại.

Subtask

$30\mathrm{\%}$ số test có $n,q\le 1000$.

Ví dụ

Đầu vào:

9 3
1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
1 1
2 2
1 9

Đầu ra:

N
Y
Y

Giải thích

• Trong test con đầu tiên, phân số $\frac{1}{9}=1,3333...$ là vô hạn tuần hoàn.
• Trong test con thứ hai, phân số $\frac{2}{8}=0,25$ là hữu hạn.
• TRong test con thứ ba, phân số $\frac{1.2.3.4.5.6.7.8.9}{9.8.7.6.5.4.3.2.1}=1$ là hữu hạn.