Division of the Kingdom
In the kingdom of ByteLand, the current ruler, Bytezar the Great Nest, wishes to prepare his heirs for governance by dividing his realm into duchies to be distributed among them. However, Bytezar faces a challenge: he has an exceptionally large number of children.
To prevent conflicts over inheritance, Bytezar has decided that each duchy must have a unique area. If necessary, some of the younger heirs may not receive a duchy.
The kingdom is represented as a rectangle of size n×m, divided into n·m unit squares. Each duchy must consist of a whole number of these unit squares and must be connected by sides. This means there must be a path between any two unit squares within a duchy, where each square in the path shares a side with the next. Every square must belong to exactly one duchy.
The goal is to divide the kingdom in such a way that the maximum number of heirs receive their duchies. Your task is to help Bytezar achieve this.
Input
The input consists of a single line with two integers n and m (1 ≤ n, m ≤ 1000), which represent the dimensions of the rectangle.
Output
First, output a single integer k, which is the maximum number of heirs who can receive their duchies. Then, for each of the following n lines, output m characters. These characters should be uppercase Latin letters from the set {A, ..., Z}, representing the duchies. Each duchy is a connected region marked by identical letters, and adjacent duchies must be marked by different letters. Note that different duchies can use the same letter. Additionally, the number of squares in any two duchies must differ.
It is guaranteed that any valid partition can be labeled according to these rules using no more than 26 letters.