Cho một dãy gồm ~N~ số nguyên dương ~A_1,A_2,\dots,A_N~. Mỗi số hạng ~A_i~ trong dãy được gán một giá trị màu tương ứng là ~B_i~. Ta định nghĩa tổng liên kết của dãy số ~A~ là tổng của các ước chung lớn nhất của các cặp giá trị ~(A_i,A_j)~ có cùng màu, tức thoả mãn ~B_i=B_j~.

Ví dụ: Dãy ~A=(4,3,6,2,4)~ có dãy màu tương ứng là ~B=(1,1,2,2,1)~. Các cặp số cùng màu là:

• ~(1,2), \gcd\{a_1,a_2\}=1~

• ~(1,5), \gcd\{a_1,a_5\}=4~

• ~(2,5), \gcd\{a_2,a_5\}=1~

• ~(3,4), \gcd\{a_3,a_4\}=2~

Do đó tổng liên kết của dãy ~A~ là ~1+4+1+2=8~.

Bạn được cho dãy số hạng ~A~ và dãy màu ~B~ tương ứng. Bạn cần thực hiện ~Q~ truy vấn, mỗi truy vấn gồm hai số nguyên dương ~p_j~ và ~t_j~ mô tả thao tác gán màu ~t_j~ cho số hạng ở vị trí ~p_j~. Bạn hãy cập nhật tổng liên kết của dãy ~A~, trước khi thực hiện truy vấn thứ nhất, và sau mỗi lần thực hiện ~Q~ truy vấn.

Input

• Dòng ~1~: Chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N,Q \le 2 \cdot 10^5)~.

• Dòng ~2~: Chứa ~N~ số nguyên dương ~A_1,A_2,\dots,A_N~ ~(1 \le A_i \le 3 \cdot 10^5)~.

• Dòng ~3~: Chứa ~N~ số nguyên dương ~B_1,B_2,\dots,B_N~ ~(1 \le B_i \le N)~.

• Dòng ~4 \rightarrow Q+3~: Mỗi dòng chứa hai số nguyên ~p_j~ và ~t_j~, thể hiện thao tác cập nhật ~B_{p_j}=t_j~.

Output

Gồm ~Q+1~ dòng:

• Dòng ~1~: Một số nguyên là tổng liên kết của ~n~ số khi chưa biến đổi.

• Dòng ~2 \rightarrow Q+1~: Mỗi dòng chứa một số nguyên là tổng liên kết của ~n~ số sau một phép biến đổi.

Scoring

Sample Input 1

5 3
4 3 6 2 4
1 1 2 2 1
1 2
2 2
2 3

Sample Output 1

8
7
11
6