Cho dãy số nguyên dương ~a_1, a_2, \ldots, a_N~ có ~N~ phần tử. Việt Anh định nghĩa hàm ~f(i, j)~ là tổng của tất cả giá trị ~\frac{a_i \times a_j}{d^2}~ với ~d~ là một ước chung của ~a_i~ và ~a_j~. Ước chung của hai số nguyên dương ~x, y~ là số tự nhiên ~d~ mà ~x, y~ đều chia hết cho ~d~.

Ví dụ dãy ~A = \{2, 1, 4\}~ thì ~f(1, 3) = (2 \times 4)/1^2 + (2 \times 4)/2^2 = 10~ với ~\{1, 2\}~ là các ước chung của 2 và 4, ~f(1, 2) = (2 \times 1)/1^2 = 2~ và ~f(2, 3) = (1 \times 4)/1^2 = 4~.

Tổng GCDS của dãy số chính là tổng tất cả các ~f(i, j)~ định nghĩa ở trên sao cho ~1 \leq i < j \leq N~. Dãy ~A = \{2, 1, 4\}~ có tổng GCDS là ~f(1, 2) + f(1, 3) + f(2, 3) = 16~.

Việt Anh biết các bạn trường THPT Chuyên Lê Quý Đôn học lập trình rất tốt nên đưa ra bài toán như sau: Cho dãy số nguyên dương ~a_1, a_2, \ldots, a_N~ có ~N~ phần tử cần tính tổng GCDS của dãy số. Ngoài ra, Việt Anh còn thực hiện thêm ~Q~ truy vấn, với mỗi truy vấn cho hai số ~(x, y)~ gán phần tử ~a_x = y~. Hãy tính tổng GCDS của dãy số mới.

Yêu cầu: Cho dãy số nguyên dương ~a_1, a_2, \ldots, a_N~ có ~N~ phần tử, thực hiện:

• Tính tổng GCDS của dãy số ban đầu;

• Trả lời ~Q~ truy vấn, với mỗi truy vấn ~(x, y)~ hãy tính tổng GCDS của dãy số sau khi cập nhật ~a_x = y~.

Input

Dữ liệu vào từ tệp văn bản GCDS.INP có cấu trúc sau:

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~ (~1 \leq N, Q \leq 5 \times 10^5~);

• Dòng thứ 2 ghi dãy ~a_1, a_2, \ldots, a_N~ (~1 \leq a_i \leq 5 \times 10^5~);

• ~Q~ dòng tiếp theo, mỗi dòng ghi hai số ~x~ và ~y~ biểu thị truy vấn gán ~a_x = y~ (~1 \leq x \leq N~, ~1 \leq y \leq 5 \times 10^5~).

Output

Kết quả ghi ra tệp văn bản GCDS.OUT gồm:

• Dòng đầu tiên ghi phần dư của tổng GCDS của dãy số ban đầu khi chia ~10^9 + 7~;

• ~Q~ dòng tiếp theo, mỗi dòng ghi một số là phần dư của tổng GCDS của dãy khi chia ~10^9 + 7~ tương ứng với thứ tự truy vấn trong tệp dữ liệu vào.

Scoring

Sample Input 1

2 2
2 4
1 4
1 3

Sample Output 1

10
21
12

Sample Input 2

4 3
462955 253652 126897 278176
2 5432
1 2314
3 2

Sample Output 2

57273948
41211035
109845881
827916911