分数: 425 点
问题陈述
有一个无限大的二维网格。细胞颜色 (x,y) 为黑色,如果 0 \leq x \leq X-1 和 0 \leq y \leq Y-1,否则为白色。
N 巨大的风暴在这个网格上按顺序发生。的 i-th 大风暴根据字符表示的规则更新网格上每个单元格的颜色 C_i 和整数 A_i, B_i.
在 i-th大风暴,细胞的颜色 (x, y) 大风暴过后是:
- 万一 C_i is
X,- if x < A_i,它变成单元格的颜色 (x, y + B_i) 大风暴之前;
- if x \geq A_i,它变成单元格的颜色 (x, y - B_i) 大风暴之前。
- 万一 C_i is
Y,- if y < A_i,它变成单元格的颜色 (x + B_i, y) 大风暴之前;
- if y \geq A_i,它变成单元格的颜色 (x - B_i, y) 大风暴之前。
两个黑色单元格 (x_1, y_1), (x_2, y_2) 是 相邻 当且仅当 |x_1 - x_2| + |y_1 - y_2| = 1。另外,还有两个黑细胞 c_1, c_2 是 已连接 当且仅当一个人可以从单元格中移动 c_1 到单元格 c_2 通过重复移动到相邻的黑色单元格。
非空集 黑色单元格的 S 是 连接的组件 当且仅当 S 满足以下条件:
- 中的任意两个单元格 S 已连接。
- 每个黑色单元格都不在 S 未连接到任何单元格 S.
毕竟是为了格子 N 大风暴发生了,求连通分量的数量并输出每个连通分量中的单元格数量 按升序排列.
约束
- N, X, Y 是整数。
- 1 \leq N \leq 14
- 1 \leq X,Y \leq 10^8
- C_i is
XorY. - A_i, B_i 是整数。
- -10^8 \leq A_i, B_i \leq 10^8
输入
输入由标准输入按以下格式给出:
N X Y C_1 A_1 B_1 \vdots C_N A_N B_N
输出
输出两行。
第一行应包含由黑色单元格组成的连接组件的数量。
第二行应包含每个连接组件中的单元格数量,以空格分隔, 按升序排列.
示例输入 1
2 3 5 X 2 2 Y -1 1
示例输出 1
2 2 13
由于大风暴,网格发生如下图所示的变化(向右方向为正方向) x- 轴,向上方向为正方向 y-轴)。

在最终网格中,存在以下两个连通分量:
- 由单元组成的连接组件 (-1,-2), (0,-2).
- 由单元组成的连接组件 (1,-1), (1,0), (1,1), (1,2), (2,-1), (2,0), (2,1), (2,2), (3,2), (3,3), (3,4), (3,5), (3,6).
注意必须输出每个连通分量中的单元格数量 按升序排列.
示例输入 2
14 68875272 94216928 X 1630731 32914676 X 17164413 -33684569 X 26798060 5418308 X 34094469 -45675954 X 43889566 34125482 X 56836569 -22217058 X 64045210 27857939 Y -54561094 11587606 Y 93548188 32214521 Y -77361096 25750481 Y 27724899 1810420 Y 80945185 -7871305 Y 14782822 -2565089 Y 54687684 -22884393
示例输出 2
8 21105046168287 22050167303226 33624667752182 223328231190194 441936776830492 1141371400772596 1141702254882183 3464097998105256
输出值可能不适合 32 位整数。