Problem D. Das mouse legacy ≡

Statement

The great and modern underwater city of R'Lyeh occupies vast area on the ocean floor. It is surrounded by R'Lyeh Ring Road (RRR) which separates business and cultural center from the rest of the city. The road itself is nothing more than a traffic pattern, which all underwater vehicles should obey.

The ocean floor around the city is flat, and vehicles can only crawl, not swim, so the road can be represented by a two-dimensional map.

Denizens of R'Lyeh built their first vehicles based on design brought to them by the famous explorers named Pinky and Brain, who visited R'Lyeh during their expedition to sunken "Titanic".

That design had one shortcoming — the vehicles were only able to turn to the right. Such a bizarre engineering solution had a serious impact on the design of RRR: it is possible to depart from any point on the road, make one or more circles around the business center and return to the starting point place, having visited all the road and making right turns only.

The traffic is one-way everywhere, so driving around R'Lyeh is simple. The only complication is a necessity to pass intersections. When passing an intersection, vehicles must move straight ahead (i.e. turns on intersections are forbidden).

Recent technical and magical advancements allowed R'Lyeh engineers to create a new class of vehicles, capable of turning either right or left. After providing all citizens with new vehicles, it became possible to convert some intersections into turn pairs (see picture) to further simplify the life in R'Lyeh. THe conversion must preserve the direction of traffic on each road segment.

The One Who Dreams in the Deep calls for your help. You must plan how to convert a maximum possible number of intersections into turn pairs, without breaking RRR connectedness.

Input file format

First line of the input file contains integers W H. Following H lines contain W symbols each and represent a map of R'Lyeh Ring Road.

Used symbols are: '│' (ASCII 179), '─' (ASCII 196), '┌' (ASCII 218), '└' (ASCII 192), '┘' (ASCII 217), '┐' (ASCII 191), '┼' (ASCII 197, represents intersection), ' ' (ASCII 32).

NOTE: the input files are in DOS (aka CPP866) encoding. Copying samples from the problem text will not work unless you convert the encoding. You can download actual input files for the samples here: Sample 1 Sample 2.

It is guaranteed that somewhere on the map there exists an area of business and cultural center, which is always seen by the right hand when moving along the RRR.

Output file format

First line of output file should contain an integer K — maximal number of crossings that can be converted into turn pairs.

Following K lines should contain a sequence of integer pairs, separated by spaces — coordinates of these crossings. Each pair consist of row and column numbers of input matrix respectively. Numeration starts from 0, so upper-left corner of input matrix has coordinates 00.

Constraints

2 ≤ W, H ≤ 20

Sample tests

4 12
            
            
  ┌────────┐
  └────────┘

0

5 9
         
      ┌┐ 
     ┌┼┼┐
     └┼┘│
      └─┘

2
2 6
2 7