线段树（Segment Tree）是一种二叉树，可视为树状数组的变种，最早出现在 2001 年，由程式竞赛选手发明。此数据结构实际应用用途不大，但由于其程式易于实作而被广泛应用于程式竞赛当中。其用途是在 O(log N ) 查询一个指定区间内的信息，并可在同样的时间复杂度支持更新等操作。
    为了学习线段树，你得到了一个长度为 n 的数组 a（下标从 1 开始），所有元素初始值均为 0 。你需要进行 q 次操作，操作有三种：
    1 x y 表示：把 a[x] 的值修改为值修改为 y 。
    2 x y 表示：把 a[x] 的值修改为值修改为 a[x] + y 。
    3 y 表示：把数组中全部的值修改为 y 。
    进行每次操作之后，你都要查询数组中所有元素的和。
    本来这道题是在仙人掌上对一条路径操作并支持历史版本查询，鉴于这只是一套 NOIP 模拟题的签到题，你只需要解决这个弱化版的问题。

第1 行为两个整数 n, q ，以空格隔开。

接下来 q 行，每行格式为 1 x y 或 2 x y 或 3 y 。

输出 q 行，每行表示进完当前操作后数组中所有元素的和。

于 10% 的数据，n = 1, q ≤ 10 。

对于 40% 的数据，n ≤ 1000 q ≤ 1000 。

对于 70% 的数据，n ≤ 1000000 q ≤ 100000。

对于 100% 的数据，1 ≤ n ≤ 10000000, 1 ≤ q ≤ 1000000,

1 ≤ x ≤ n, 0 ≤ y ≤ 100 。

本题输入规模较大，为减小输入数据需要的时间对你的程序效率造成的影响，在下发文件里提供了一个基于fread的输入输出模板。如果你要使用该模板，请在文件输入输出而不是标准输入输出下测试你的程序。

SDSC2018