M. Compress (500 points)

One under-lieutenant of Bertie's gang likes to solve word puzzles in his head. Some people are just like that.

In this particular puzzle, given a list of words, you have to write down all words on the same graph paper. The graph paper has cells, where X=0 is the leftmost column, Y=0 is the topmost row. The paper can be considered infinite (within reasonable limits) towards the right and the bottom.

For each word, you have to specify the cell for the first letter of the word (by X, Y), and a direction: h for horizontal, v for vertical. Horizontal words are written from left to right, vertical words from top to bottom.

You cannot overwrite a letter already on paper by a different letter, but otherwise, words may share letters, if the letter is the same as the one already in the cell.

This is a scaled task - for each input, the team who uses the least number of cells to write all words, wins.

Input Format

Words are given surrounded by free-form whitespace.

Output Format

Each line must look like:

X Y dir

Where X, Y are the cell coordinates, and dir is either h or v.

There should be exactly as many lines as are words in the input file. Each output line should specify the position and orientation of the corresponding input word.