You're a member of the custodial staff at a large convention centre. You came in for your shift this morning to find that the contractors painting the ceiling overnight had an accident and now there's a huge paint stain on the floor. It's already dried. The boss wants you to do something about it.

Fortunately, the convention centre has a huge stock of square carpet tiles in a range of sizes that you can put down on the floor to cover the stain. These carpet tiles are so thin that you can overlap them as much as you want without creating a tripping hazard, but you know from past experience that the boss is really picky about how you place them.

The floor of the convention centre is divided into a grid such that each square in the grid is $1$m $\times$ $1$m. The boss likes the carpet tiles to be placed so that each grid square is either totally covered or totally uncovered. The boss will not like it if you put carpet tiles over any grid square that does not have at least a little bit of paint on it. The boss will also not like it if you try to place a rug that doesn't fit within the boundaries of the convention centre floor.

The input will contain $10$ test cases. Each test case will consist of $N$ lines of $N$ characters each $(1\le N\le 200)$, representing the grid squares of the convention centre floor. Any grid square with paint on it is marked with an asterisk character (ASCII code $42$). Grid squares with no paint on them are indicated with a hyphen character (ASCII code $45$).

Your job is to output a single integer $M$ for each test case $(M>0)$ to indicate the minimum number of rugs required to cover the spill without covering any grid squares that are not part of the spill. This should be followed by $M$ lines, each representing one of the $M$ rugs in your solution. Each rug is represented by three integers $T,L$ and $S$ representing its top row, leftmost column and size. The coordinate system starts at $(0,0)$ and increases downwards for rows and to the right for columns. You can assume that you have an unlimited supply of $S\times S$ rugs of all sizes ($1\le S\le 200$, in metres).

Note that the sample input below only contains $2$ test cases, but the real data files will contain $10$.

Sample Input

-----
--***
-***-
-**--
-----
----------
--**------
--****----
--******--
--******--
---*****--
---*****--
-----**---
-----**---
------*---

Sample Output

3
2 1 2
1 2 2
1 4 1
7
3 4 4
2 2 3
7 5 2
3 3 4
1 2 2
2 3 3
9 6 1

Notes on Grading

Your output will be scored by a judging app which will assign a base score of $5$ points for each solution that is valid (all the squares with paint on them are covered and no squares without paint are covered) and then up to $5$ more points based on how close the size of your solution was to the target size.

Be sure that your data file matches the required output format exactly. The judging app might be able to recover from badly formatted or invalid data, or it might not. If your data is not formatted exactly correctly, you might get some points or you might get nothing.

Question Development Team

Sam Scott (Sheridan College)
Kevin Forest (Sheridan College)
Stella Lau (University of Cambridge)
Dino Baron (University of Waterloo)
Greg Reid (St. Francis Xavier Secondary School, Mississauga)
John Ketelaars (ECOO-CS Communications)
David Stermole (ECOO-CS President)

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org