题目描述

你的面前有一个长度为 $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次操作结束后，数组变为{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$。