给定一个矩阵,由 $$$n$$$ 行和 $$$m$$$ 列组成。
您可以对其执行两种类型的操作:
- 将整个列涂成蓝色;
- 将整行涂成红色。
请注意,您无法选择绘制行或列的颜色。
在一秒钟内,您可以执行一个操作或同时执行多个操作。如果您执行一项操作,它将是免费的。如果您同时执行 $$$k > 1$$$ 操作,将花费 $$$k^2$$$ 金币。当同时执行多个操作时,对于受两种类型操作影响的每个单元格,可以独立选择颜色。
您需要处理 $$$q$$$ 查询。在每次查询之前,所有单元格都变为无色。最初,任何单元格的颜色都没有限制。在第 $$$i$$$ 查询中,添加以下形式的限制:
- $$$x_i~y_i~c_i$$$ — $$$x_i$$$ 列 $$$y_i$$$ 中的单元格应涂成 $$$c_i$$$ 颜色。
因此,在 $$$i$$$ 查询之后,对矩阵单元所需的颜色有 $$$i$$$ 限制。每次查询后,输出根据限制绘制矩阵的最小成本。
输入
第一行包含三个整数 $$$n、m$$$ 和 $$$q$$$ ($$$1 \le n, m, q \le 2 \cdot 10^5$$$) - 矩阵的大小和查询的数量。
在接下来的 $$$q$$$ 行的第 $$$i$$$ 行中,两个整数 $$$x_i、y_i$$$ 和一个字符 $$$c_i$$$ ($$$1 \le x_i \le n$$$; $$$1 \le y_i \le m$$$; $$$c_i \in$$$ {'R', 'B'},其中 'R' 表示红色,'B' 表示蓝色)—第 $$$i$$$ 限制的描述。所有查询中的单元格都是成对不同的。
输出
打印 $$$q$$$ 整数 - 在每次查询后,输出根据限制绘制矩阵的最小成本。
示例
输入 #1
2 2 4 1 1 R 2 2 R 1 2 B 2 1 B
输出 #1
0 0 0 16
输入 #2
3 5 10 1 1 B 2 5 B 2 2 B 2 3 R 2 1 B 3 2 R 3 3 B 1 2 R 1 3 B 3 1 B
输出 #2
0 0 0 0 0 0 16 16 25 25