Cho $n$ số nguyên dương $a_1,a_2,...,a_n$. Với mỗi truy vấn dạng $(l,r,b)$ sao cho $1\le l\le r\le n$ và số $b$ nguyên dương, xác định số $b$ cần được viết liền nhau ít nhất bao nhiêu lần để thu được một số là bội của các số $a_l,a_{l+1},...,a_r$.

Đầu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $q$ $(1\le n,q\le 10000)$, lần lượt là số phần tử của dãy số và số lần truy vấn.

Dòng tiếp theo chứa $n$ số nguyên trong khoảng $[1,{10}^6]$ là các phần tử của dãy số $(a)$.

$q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn gồm ba số $(l,r,b)$ với $1\le l,r\le n$ và $1\le b\le {10}^6$.

Đầu ra

$q$ dòng, mỗi dòng chứa duy nhất một số nguyên là kết quả của truy vấn: Nếu không tồn tại số nguyên thỏa mãn đề bài thì xuất ra $-1$, trong trường hợp còn lại xuất ra kết quả lấy phần dư cho ${10}^9+7$.

Subtask

$20\mathrm{\%}$ số test có $n=q=1$.

$20\mathrm{\%}$ số test có $n=1$.

$20\mathrm{\%}$ số test có $q=1$.

$40\mathrm{\%}$ số test còn lại không có giới hạn gì thêm.

Ví dụ

Đầu vào

3 4
1 2 3
1 3 22
1 3 1
3 3 7
1 2 4

Đầu ra:

3
-1
3
1

Giải thích: Trong truy vấn đầu tiên, số $222222$ (lặp lại $3$ lần số $22$) là bội của $1,2$ và $3$.