Alex is playing a game with William. Alex gets two sequences: sequence ~A~ and sequence ~W~, each of which has ~N~ numbers. Alex will show William the sequence ~W~ but not the sequence ~A~. The objective of this game is to figure out each number in sequence ~A~.

During the game, William can ask Alex questions as many times as he wants. For each question, William will pick up an interval ~[L, R]~ (~1 \le L \le R \le N~) and ask Alex the sum of ~a_i~ for ~i \in [L, R]~. Alex will answer William's question, but will charge William for ~\gcd(w_L, w_{L+1}, \dots, w_R)~ dollars. William wants to use the minimal cost to figure out the sequence ~A~.

Since William is bored, he decides to play this game for ~Q~ rounds. Before each round, Alex will re-generate the sequence ~A~. However, Alex is too lazy to re-generate the cost sequence ~W~. So, Alex will only change one number from the previous sequence ~W~. Given the number which Alex will change and the new value, can you help William to find out the minimum cost for figuring out the sequence ~A~ in each round of the game?

Constraints

For all subtasks:

~1 \le N, Q \le 10^5~

~1 \le a_i, w_i \le 10^9~

~1 \le L \le R \le N~

~1 \le p \le N~.

Subtask	Points	Additional constraints
~1~	~14~	~N \le 200~, ~Q \le 200~
~2~	~21~	~N \le 10^5~, ~Q = 1~
~3~	~23~	~N \le 10^5~, ~Q \le 1\,000~
~4~	~42~	No additional constraints.

Input Specification

The first line contains two integers, ~N~ and ~Q~, the number of elements in each sequence and the number of rounds William will play.

The second line contains ~N~ integers, the initial sequence ~W~.

~Q~ lines of input follow. The ~i^{th}~ line contains two integers, ~p~ and ~w_p~, which means Alex will pick up the ~p^{th}~ element from the previous sequence ~W~ and replace it with the new value ~w_p~ before round ~i~.

Output Specification

Print ~Q~ lines. The ~i^{th}~ line contains one integer, the minimum cost for William to figure out the sequence ~A~ in game ~i~.

Sample Input

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

Sample Output

5
6
10

Explanation for Sample Output

The initial sequence ~W~ is ~[1, 2, 3, 4, 5]~.

Before round ~1~, Alex will change ~w_1~ to be ~2~, i.e. the new sequence ~W~ is ~[2, 2, 3, 4, 5]~.

In round ~1~, William can ask questions for ~[1, 5]~, ~[1, 4]~, ~[2, 5]~, ~[1, 3]~ and ~[3, 5]~ with the total cost of ~5~.

Before round ~2~, Alex will change ~w_3~ to be ~4~, i.e. the new sequence ~W~ is ~[2, 2, 4, 4, 5]~.

In round ~2~, William can ask questions for ~[1, 5]~, ~[2, 5]~, ~[3, 5]~, ~[4, 5]~ and ~[1, 4]~ with the total cost of ~6~.