Sum of Expressions with Updates

You are given a sequence of n numbers: \(a_1, a_2, \dots, a_n\). Between every two adjacent numbers, you may insert one of three operators: plus (+), minus (-), or multiply (*). Thus, there are \(3^{n-1}\) possible expressions if the operators are chosen independently.

All expressions are evaluated from left to right (i.e. no operator precedence is applied). For example, for \(n=3\) the expression \[ a_1 \;\texttt{+}\; a_2 \;\texttt{*}\; a_3 \] is evaluated as \((a_1+a_2)*a_3\), not as \(a_1+(a_2*a_3)\).

You are interested in the sum of the values of all \(3^{n-1}\) expressions. In fact, it can be shown that if the numbers are not changed, the sum of all expressions is given by \[ a_1 \prod_{i=2}^{n}(2+a_i), \] because when processing the sequence from left to right each new number \(a_i\) contributes a factor \(2+a_i\) (corresponding to the fact that choosing + or - each finalize the previous partial result, while * continues the multiplication).

To make the problem more interesting, you must support update queries. In each query, you are provided with an index \(i\) and a new value \(x\), meaning that \(a_i\) is permanently changed to \(x\). After every update, output the new value of \[ a_1 \prod_{i=2}^{n}(2+a_i). \]

inputFormat

The first line contains two integers \(n\) and \(q\) — the number of numbers and the number of update queries respectively.

The second line contains \(n\) space-separated integers representing the initial sequence \(a_1, a_2, \dots, a_n\).

Each of the following \(q\) lines contains two space-separated integers \(i\) and \(x\), indicating that the value of \(a_i\) is updated to \(x\). (Note that the updates are permanent.)

outputFormat

For each update query, output a single line containing the new sum of the values of all expressions, which is given by \[ a_1 \prod_{i=2}^{n}(2+a_i). \]

sample

3 2
1 2 3
2 3
1 2

25
50