Cho dãy số nguyên dương ~a_1, a_2, \dots, 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ị ~(a_i \cdot 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 \cdot 4)/1^2 + (2 \cdot 4)/2^2 = 10~ với ~\{1,2\}~ là các ước chung của ~2~ và ~4~, ~f(1,2) = (2 \cdot 1)/1^2 = 2~ và ~f(2,3) = (1 \cdot 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 \le i < j \le N~. Dãy ~A = \{2, 1, 4\}~ tổng GCDS của dãy số 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, \dots, 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, \dots, a_N~ có ~N~ phần tử, thực hiện:

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

• 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 dãy đã được thay đổi.

Input

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

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

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

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• 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