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\%\) số test có \(n = q = 1\).

\(20\%\) số test có \(n = 1\).

\(20\%\) số test có \(q = 1\).

\(40\%\) 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\).