题目描述

有一个类似俄罗斯方块的拼图游戏，所有拼图都由不超过 3 个小方格组成。共有 4 类拼图：

• 1x1；
• 2x1；
• 3x1；
• L 形三格拼图。

考虑旋转后，这些拼图共有 9 种不同摆放方式。

现在分别给出四类拼图的数量。你需要把所有拼图放在一个网格中，使得被拼图占据的所有小方格形成一个环。也就是说：

• 每个被占据的小方格在上下左右四个方向中恰好有 2 个相邻的被占据小方格；
• 环内部区域在四连通意义下连通。

输入格式

输入一行四个整数 a b c d，分别表示 1x1、2x1、3x1、L 形拼图的数量。

输出格式

第一行输出两个整数 n m，表示答案矩阵的行数和列数。

接下来输出 n 行，每行 m 个整数。每个位置的含义如下：

• 0：该位置为空；
• i：该位置属于编号为 i 的拼图。

所有拼图编号应为 1..a+b+c+d，且不同拼图编号不同。同一块拼图占据的格子应使用同一个编号。

合法性要求

一个输出合法当且仅当：

• 矩阵大小不超过 800 x 800；
• 每个被占据的小方格恰好有 2 个四邻接方向上的被占据小方格；
• 被占据区域形成一个环；
• 环内部区域四连通。

数据范围与约定

• 保证输入一定有解；
• 30 分：10 <= a,b,c,d <= 100；
• 50 分：5 <= a,b,c,d <= 100；
• 80 分：3 <= a,b,c,d <= 100；
• 100 分：2 <= a,b,c,d <= 100。

样例

3 4 3 4

一种合法输出为：

11 6
0 1 2 4 4 4
1 1 0 0 0 3
8 0 0 0 3 3
8 0 0 0 9 0
8 0 0 0 9 9
10 0 0 0 0 13
10 0 0 0 0 11
12 0 0 0 0 11
12 0 0 0 0 14
6 0 0 0 0 7
6 5 5 5 7 7

样例构造示意：

下面的矩阵不是合法解，因为存在格子邻居数不是 2，且内部区域不连通：