Problem F. FEFU swarm ≡

Statement

Scientists of Far Eastern Federal University have put serious effort into design and construction of collectives of interconnected robots, known as robot swarms.

To demonstrate their research, scientists decided to program robots to move in beautiful patterns in front of an audience.

Robots are located on a flat field divided into N by M square cells. Each robot takes exactly one square. To keep their connection, each robot must have another robot in one of the cells with a common side to its cell. Each second, exactly one of the robots may move into any of 8 neighbor cells, provided the destination cell was free and the robot will remain connected at the destination cell.

Initially robots are positioned in a horizontal row starting from the bottom left corner of the field.

Target pattern is a 4-connected set of cells (i.e. every cell of the pattern is connected to at least one other cell of the pattern). There are no holes inside the pattern.

Your program must, given description of a field and a target pattern, find such a sequence of robot moves that after executing it all cells of the pattern will be occupied by robots. Total number of moves in the sequence must not exceed 10⁶. Robots are allowed to temporarily move off the field during the sequence.

Input file format

First line of input file contains integers N M — field size. Following N lines contain M characters each.

Each character may be one of: '#' (ASCII 36)  — robot on initial position, '.' (ASCII 46)  — free cell, '*' (ASCII 42) — free cell which is a part of target pattern. It is guaranteed that number of robots equals number of target cells. There are at least 2 robots.

Output file format

Output file must contain integer C — number of robot moves, followed by C move descriptions.

Each move description must contain 4 integers i₁ j₁ i₂ j₂ — coordinates (row and column numbers) of source and destination cells for a robot move. Rows are numbered from 1 to N top to bottom. Columns are numbered from 1 to M left to right.

If there is more than one solution, output any of them.

Constraints

2 ≤ N, M ≤ 100, C ≤ 10⁶

Sample tests

4 4
..**
...*
....
###.

10
4 1 3 2
3 2 3 3
4 2 3 2
3 2 2 3
4 3 3 4
2 3 2 4
3 3 2 3
2 3 1 4
3 4 2 3
2 3 1 3