题目描述

徐老师的面前有一个长度为 $n$ 的数组。初始时，第 $i$ 个位置的元素为 $i$（即所有位置上的元素依次为从 $1$ 到 $n$ 的正整数）。

接下来，你需要帮徐老师依次完成 $m$ 个操作。每个操作可能是：

• A $p$ $q$，表示你需要修改数组中的所有元素。具体地，第 $i$ 个位置的元素被修改成 $p \times i + q$。
• B $x$ $y$，表示你需要修改数组中的单个元素。具体地，第 $x$ 个位置的元素被修改成 $y$。

其中上述 $p,q,x,y$ 均为整数。

每次操作结束后，你需要输出数组中所有元素的和。

输入格式

从标准输入读入数据。

输入的第一行包含两个数 $n, m$。

接下来 $m$ 行，每行依次表示一个操作，格式为 A $p$ $q$ 或者 B $x$ $y$，意义如上所述。

同一行输入的相邻两个元素之间，用一个空格隔开。

输出格式

输出到标准输出。

输出共 $m$ 行，每行表示每个操作结束之后，数组中所有数的和。

样例

5 4
B 1 5
A -1 0
A 1 2
A 2 -5

19
-15
25
5

样例1解释

• 第 $1$ 次操作结束后，数组变为 $[5, 2, 3, 4, 5]$；
• 第 $2$ 次操作结束后，数组变为 $[-1, -2, -3, -4, -5]$；
• 第 $3$ 次操作结束后，数组变为 $[3, 4, 5, 6, 7]$；
• 第 $4$ 次操作结束后，数组变为 $[-3, -1, 1, 3, 5]$。

50000000 4
A 1 0
A 1000 0
A 1000 1000000000
B 50000000 -1000000000

1250000025000000
1250000025000000000
1300000025000000000
1299999973000000000

数据范围

对于测试点 $1,2$，保证 $n \leq 100$。

对于测试点 $3,4$，保证所有的操作均为 B 类型。

对于测试点 $5,6,7,8$，保证所有的操作均为 A 类型。

对于所有数据，保证 $n \leq 50,000,000, m \leq 500,000$。对于每个操作，保证 $|p| \leq 1000, |q|,|y| \leq 10^9, 1 \leq x \leq n$。