Processing math: 100%

Problem D. Digital circuit

Author:A. Baranov   Time limit:1 sec
Input file:Standard input   Memory limit:512 Mb
Output file:Standard output  

Statement

Let there be a rectangular ASCII-art image of a digital circuit, composed of logical elements and wires connecting them.

Logical elements are represented as rectangular areas bordered by '#' (ASCII 35) characters.

Each element always contains a description composed of digits and small Latin letters.

Description may be split into several parts, separated by spaces, and span multiple lines.

Wires are represented as sequences of '.' (ASCII 46) characters.

The rest of the circuit is filled with spaces.

Any two elements can not be adjacent to each other (there is always space between them).

Wires can only connect at 90 angle.

Parallel wires can not be adjacent to each other (there is always space between them).

An element is considered connected to a wire if their characters are adjacent either horizontally or vertically.

Wires can not cross area occupied by an element.

Bus is a set of connected wires.

Given the image, determine the set of logical elements and buses connected to them.

Input format

Input contains an ASCII image.

Output format

Output the number of logical elements N,
followed by N lines, with each line containing a description of a single element.
Parts of a description must be separated by spaces.

Order of elements in output must correspond to the order at which elements occur
in the input image when traversing by rows from the top-left corner.

Next, output the number of buses M, followed
by sets of connected elements.

Each set starts with a number of elements in it,
followed by element indices
(starting from zero).

Constraints

Total number of characters in the image does not exceed 106.

Sample tests

No. Standard input Standard output
1
           #####        
#######    #abc#        
# xyz #    #123#        
#     #....#####   #####
#######    .       #   #
           .    ...#abc#
............    .  #   #
.               .  #####
. ############  .       
. #  123     #  .       
. #    xyz   #........  
. ############       .  
.         .          .  
...........          .  
          .    #########
          .....#  abc  #
 #######  .    #########
 #xyz  #...             
 #     #  .       ##### 
 # abc #  ........#123# 
 #######   .      ##### 
           #####        
           #xyz#        
           #####        
8
abc 123
xyz
abc
123 xyz
abc
xyz abc
123
xyz

3
6 0 3 4 5 6 7
3 2 3 4
2 0 1

0.055s 0.009s 13