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 \(i\:j\), bạn hãy kiểm tra xem phân số \(\frac{a_ia_{i + 1}...a_{j}}{b_ib_{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*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*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\%\) 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.