题目描述

Ryo and Kita are designing a new poster for Kessoku Band. After some furious brainstorming, they came to the conclusion that the poster should come in the form of a $2\text{-D}$ grid of lowercase English letters (i.e. a to z), with $N$ rows and $M$ columns.

Furthermore, it is known that Ryo and Kita both have peculiar tastes in palindromes. Ryo will only be satisfied with the poster if exactly $R$ of its rows are palindromes, and Kita will only be satisfied with the poster if exactly $C$ of its columns are palindromes. Can you design a poster that will satisfy both Ryo and Kita, or determine that it is impossible to do so?

Note: A string is considered a palindrome if it is the same when read forwards and backwards. For example, kayak and bb are palindromes, whereas guitar and live are not.

输入格式

The first and only line of input consists of $4$ space-separated integers $N, M, R$, and $C$.

The following table shows how the available $15$ marks are distributed.

输出格式

If it is impossible to design a poster that will satisfy both Ryo and Kita, output IMPOSSIBLE on a single line.

Otherwise, your output should contain $N$ lines, each consisting of $M$ lowercase English letters, representing your poster design. If there are multiple possible designs, output any ofthem.

题目大意

Ryo 和 Kita 正在为 Kessoku 乐队设计一张新的海报，他们两个人都有各自不同的审美，但都同时认为一份符合他们审美的海报的内容应该都为小写字母，且大小为 $N \times M$。Ryo 认为当有 $R$ 数量的行是回文时，这个海报是符合其审美的；Kita 认为当有 $C$ 数量的列是回文时，这个海报是符合其审美的。

现在分别给出 $N,M,R,C$，问你是否可以构造出一个 $N \times M$ 的海报满足要求，可以就输出你的方案，不行的话输出 IMPOSSIBLE。

4 5 1 2

union
radar
badge
anime

2 2 2 1

IMPOSSIBLE

提示

Explanation of Output for Sample Input $1$：

In the given design, only the second row (namely radar) and the second and third columns (namely naan and iddi) are palindromes. Since exactly $R = 1$ of the rows and $C = 2$ of the columns are palindromes, this is an acceptable design.

Explanation of Output for Sample Input $2$：

In this case, it can be proven that it is impossible to satisfy both Ryo and Kita.

本题采用捆绑测试：

• Subtask 1（2 points）：数据保证 $2 \leq N \leq 2000$，$2\leq M\leq 2000$，$R = 1$，$C = 1$。

• Subtask 2（2 points）：数据保证 $N = 2$，$M = 2$，$0\leq R\leq N$，$0\leq C\leq M$。

• Subtask 3（4 points）：数据保证 $N = 2$，$2\leq M \leq2000$，$0\leq R\leq N$，$0\leq C\leq M$。

• Subtask 4（7 points）：数据保证 $2\leq N\leq 2000$，$2\leq M \leq2000$，$0\leq R\leq N$，$0\leq C\leq M$。