P4340 [SHOI2016] 随机序列

你的面前有 $n$ 个数排成一行，分别为 $a_1,a_2,...,a_n$ 。你打算在每相邻的两个 $a_i$​​ 和 $a_{i+1}$ 间都插入一个加号、减号或者乘号。那么一共有$3^{n-1}$ 种可能的表达式。 你对所有可能的表达式的值的和非常感兴趣。但这毕竟太简单了，所以你还打算支持一个修改操作，可以修改某个 $a_i$ 的值。 你能够编写一个程序对每个修改都输出修改完之后所有可能表达式的和吗？注意，修改是永久的，也就是说每次修改都是在上一次修改的基础上进行，而不是在最初的表达式上进行。

无

无

对于20%的数据，n,q