YugiHacker có một dãy số nguyên dương ~N~ phần tử và ~Q~ truy vấn, mỗi truy vấn YugiHacker sẽ chọn ra một phần tử và nhân nó lên một lượng là ~x~, hãy tính Bội chung nhỏ nhất của dãy sau khi thực hiện mỗi truy vấn này.

Vì kết quả có thể rất lớn, bạn hãy in ra kết quả sau khi chia phần dư ~10^9 + 7~.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~N, Q~ ~(1 \leq N, Q \leq 10^5)~.
• Dòng tiếp theo là ~N~ số nguyên ~a_i~ ~(1 \leq a_i \leq 10^5)~.

• ~Q~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên ~i~, ~x~ ~(1 \le i \le n, 1 \le x \le 10^5)~.

• Input sẽ có dạng:

N Q
a1 a2 a3 ... aN
i1 x1
i2 x2
...
iQ xQ

Output

• Với mỗi truy vấn in ra kết quả trên 1 dòng.

Sample

Input #1

5 3
1 2 3 4 5
2 2
1 7
5 18

Output #1

60
420
1260