题目描述

许多绘图程序都有统计图片中各种颜色像素数量的功能。现在你需要模拟这一功能。

有一张边长为 $S$ 的正方形位图，共有 $S\times S$ 个像素。像素坐标范围为 $0\sim S-1$，左上角坐标为 $(0,0)$，右下角坐标为 $(S-1,S-1)$。初始时，所有像素的颜色均为 $0$。

共有 $M$ 条绘图命令，需要按照输入顺序依次执行。颜色编号均为 $0\sim 9$。命令有以下五种：

• PIXEL x y c：将像素 $(x,y)$ 的颜色修改为 $c$。
• HLINE x1 y x2 c：将从 $(x_1,y)$ 到 $(x_2,y)$ 的整条水平线段上的像素全部修改为颜色 $c$，两个端点均包含在内。
• VLINE x y1 y2 c：将从 $(x,y_1)$ 到 $(x,y_2)$ 的整条竖直线段上的像素全部修改为颜色 $c$，两个端点均包含在内。
• RECT x1 y1 x2 y2 c：以 $(x_1,y_1)$ 和 $(x_2,y_2)$ 为一对对角点，将对应的轴对齐实心矩形内所有像素修改为颜色 $c$，边界也包含在内。
• FLOODFILL x y c：设执行该命令前像素 $(x,y)$ 的颜色为 $d$。将所有与 $(x,y)$ 属于同一个颜色为 $d$ 的连通区域的像素修改为颜色 $c$。这里两个像素只有在上下或左右相邻时才视为相邻，也就是说使用四连通。

如果某个像素先后被多条命令修改，则最终颜色由最后一次影响它的命令决定。

执行完全部命令后，请统计颜色 $0,1,\ldots,9$ 各自拥有多少个像素。

输入格式

第一行输入两个整数 $M,S$，分别表示绘图命令数量和位图的边长。

接下来 $M$ 行，每行是一条命令，格式为以下五种之一：

PIXEL x y c
HLINE x1 y x2 c
VLINE x y1 y2 c
RECT x1 y1 x2 y2 c
FLOODFILL x y c

输出格式

第一行输出整数 10。

接下来输出 $10$ 行，第 $i+1$ 行输出颜色 $i$ 的像素数量，其中 $0\le i\le9$。

数据范围与约定

• $1\le S\le10^9$；
• $0\le M\le50$；
• 所有像素坐标均在 $[0,S-1]$ 范围内；
• 所有颜色编号均在 $[0,9]$ 范围内；
• 水平线、竖直线以及矩形的两个端点可以按任意顺序给出；
• 答案可能达到 $10^{18}$，需要使用 64 位整数保存。

输入输出样例 #1

输入

2 2
PIXEL 0 0 1
PIXEL 0 0 2

输出

10
3
0
1
0
0
0
0
0
0
0

说明

图片共有 $4$ 个像素。首先将 $(0,0)$ 修改为颜色 $1$，随后又将同一个像素修改为颜色 $2$。最终有 $3$ 个颜色为 $0$ 的像素和 $1$ 个颜色为 $2$ 的像素。

输入输出样例 #2

输入

9 8
VLINE 0 4 1 1
RECT 4 2 7 4 3
RECT 6 7 7 3 4
PIXEL 1 7 5
PIXEL 1 5 7
PIXEL 2 6 6
FLOODFILL 1 6 8
FLOODFILL 5 3 9
HLINE 4 6 7 3

输出

10
33
4
0
4
8
1
1
1
4
8

执行完所有操作后，$8\times8$ 位图为：

00000000
10000000
10009999
10009944
10009944
87000044
88603333
85000044

输入输出样例 #3

输入

4 10000
VLINE 3000 0 9999 1
FLOODFILL 2999 3000 2
FLOODFILL 3001 3000 3
FLOODFILL 8000 8000 3

输出

10
0
10000
30000000
69990000
0
0
0
0
0
0

说明

第一条命令画出了一条贯穿整张图片的竖线，它将原本颜色为 $0$ 的区域分成左右两个互不连通的部分，因此后续两次填充可以分别修改这两个区域。