← 返回题目列表

Codeforces · 63/D

D. 分割岛

中文机器翻译题面 查看原题

布卡岛上发生了一场革命。新政府取代了旧政府。新政府包括n个政党,每个政党根据其对革命的贡献有权获得该岛的某些部分。然而,他们无法分割岛屿。

岛屿通常可以表示为两个相应大小的矩形a × b 和c × d 单位正方形。这些矩形彼此靠近。此时,长度为 a 的一条边和长度为 c 的一条边在一条线上。您可以在图片中更详细地看到这一点。

第 i 方有权拥有等于 xi 单位平方的岛屿部分。每个这样的部分都应该完全覆盖岛的几个方格(不允许部分覆盖方格)并且是一个相连的图形。 “连通图形”预设从该方的任何方格可以移动到同一方的任何其他方格,移动穿过也属于该方的边缘相邻方格。

你的任务是在各方之间划分岛屿。

输入

第一行包含 5 个空格分隔的整数 — a、b、c、d 和 n(1 ≤ a、b、c、d ≤ 50、b ≠ d、1 ≤ n ≤ 26)。第二行包含 n 个空格分隔的数字。其中第 i 个等于数字 xi (1 ≤ xi ≤ a × b + c × d)。保证 $$\sum_{i=1}^{n} x_i = a \times b + c \times d$$。

输出

如果无法按照要求的方式在各方之间划分岛屿,请打印“NO”(不带引号)。否则,打印“YES”(也不带引号),并从下一行开始打印 max(b, d) 行,每行包含 a + c 字符。要标记哪个方格应属于哪个方,请使用小写拉丁字母。对于输入数据中顺序第一的一方,使用“a”,对于第二顺序的一方使用“b”,依此类推。使用 ”。”对于属于大海的方块。输出数据第二行的第一个符号应对应于属于矩形 a × b 的正方形。第二行的最后一个符号应对应于属于矩形 c × d 的正方形。

如果有多个解,则输出任意一个。

示例

输入 #1

3 4 2 2 3
5 8 3

输出 #1

YES
aaabb
aabbb
cbb..
ccb..

输入 #2

3 2 1 4 4
1 2 3 4

输出 #2

YES
abbd
cccd
...d
...d