# Bội chung của dãy

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 MOD $10^9 + 7$

# Input

Dòng đầu là số $2$ nguyên dương $n, q$ ($1 \le n, q \le 10^5$)

Dòng tiếp theo là $n$ số nguyên dương $a_i$ ($1 \le a_i \le 10^5$)

$q$ dòng tiếp theo, mỗi dòng là $2$ số nguyên $i, x$ ($1 \le i \le n$, $1 \le x \le 10^5$)

# Output

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

# Subtask

- Subtask 1: $q \le 10$
- Subtask 2: $a_i, x$ chỉ chia hết cho $2, 3 \text{ hoặc } 5$
- Subtask 3: Không giới hạn gì thêm

# Sample

- Input

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

- Output

60
420
1260

# Hướng dẫn giải

Xét nhân tử nguyên tố $p$, thì số mũ của $p$ trong Bội chung của dãy sẽ là số mũ lớn nhất của $p$ khi phân tích các $a_i$ thành thừa số nguyên tố.

Vậy với mỗi lần nhân $x$ vào vị trí $a_i$, ta cần kiểm tra các nhân tử $p$ của $x$, khi nhân $x$ vào $a_i$ có khiến số mũ lớn nhất đó thay đổi không, nếu có ta sẽ nhân Bội chung lên một lượng tương ứng

Số nhân tử khi phân tích một số $x$ thành thừa số nguyên tố sẽ không vượt quá $log(x)$

Độ phức tạp : $O(AloglogA + (n+q)logA)$ với $A$ là giá trị tối đa của $a_i, x$

# Code Solution

/*
    www.youtube.com/YugiHackerChannel
    oj.vnoi.info/user/YugiHackerKhongCopCode
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn 100005
#define MOD 1000000007
using namespace std;
int n, q, a[maxn], d[maxn], ma[maxn];
map <int, int> cnt[maxn];
long long ans = 1;
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    for (int i=2; i*i<maxn; ++i)
        for (int j=i*i; j<maxn; j+=i) if (d[j] == 0) d[j] = i;
    for (int i=2; i<maxn; ++i) if (d[i] == 0) d[i] = i;

    cin >> n >> q;
    f1 (i, n)
    {
        cin >> a[i];
        while (a[i] > 1)
        {
            int k = d[a[i]];
            int cur = 0;
            while (a[i] % k == 0) cur++, a[i]/=k;
            cnt[i][k] += cur;
            if (cnt[i][k] > ma[k])
            {
                f1 (_, cnt[i][k]-ma[k]) (ans *= k) %= MOD;
                ma[k] = max(ma[k], cur);
            }
        }
    }
    while (q--)
    {
        int i, val; cin >> i >> val;
        while (val > 1)
        {
            int k = d[val];
            int cur = 0;
            while (val % k == 0) cur++, val /= k;
            cnt[i][k] += cur;
            if (cnt[i][k] > ma[k])
            {
                f1 (_, cnt[i][k]-ma[k]) (ans *= k) %= MOD;
                ma[k] = max(ma[k], cnt[i][k]);
            }
        }
        cout << ans; el;
    }
}