Islands Alliance Formation

In a fantasy world there is a rectangular island, divided into R rows and C columns. Some grid cells are unoccupied, while others contain a village inhabited by one of the creatures: Elf, Human, Dwarf, or Hobbit. Villagers in the same cell form a village.

In order to defend against demonic attacks, villages need to form alliances. For every village, its neighbors are defined as the villages in the four adjacent cells (up, down, left, right).

Each creature type requires an exact number of alliance links with some of its neighbors:

• Elf: exactly 1 alliance.
• Human: exactly 2 alliances, and the two allied neighbors must not be both in the same horizontal or vertical direction (i.e. one must be horizontal and one vertical).
• Dwarf: exactly 3 alliances.
• Hobbit: exactly 4 alliances (i.e. all of its neighbors).

The alliance relationship is bi‐directional. That is, if village A allies with village B, then village B is allied with village A. Some neighboring villages may not form an alliance if not needed. Your task is to decide whether an alliance structure exists in which every village gets the required number of alliances. If so, output the alliance structure; otherwise, output Impossible!.

Note: All formulas (e.g. the grid dimensions and alliance counts) are represented in \(\LaTeX\) format. For example, the island is divided into \(R\) rows and \(C\) columns.

inputFormat

The first line contains two integers \(R\) and \(C\) (number of rows and columns). The following \(R\) lines each contain a string of length \(C\). Each character is either a dot . representing an empty cell, or one of the characters E, H, D, B representing a cell occupied by an Elf, Human, Dwarf, or Hobbit respectively.

Note: The Human requires one horizontal and one vertical alliance. The village alliance requirement for each creature is as follows:

• Elf: 1
• Human: 2
• Dwarf: 3
• Hobbit: 4

outputFormat

If a valid alliance structure exists, output the number \(M\) of alliance connections on the first line. Then output \(M\) lines, each with 4 space‐separated integers \(r_1\), \(c_1\), \(r_2\), \(c_2\) (1-indexed), indicating that the village in cell \((r_1, c_1)\) forms an alliance with the village in cell \((r_2, c_2)\).

If no valid alliance structure exists, output the line Impossible!.

sample

2 2
EE
EE

2
1 1 1 2
2 1 2 2