Mark just solved a traditional programming task: finding the shortest path in a maze. The map of his maze is a rectangular grid with r rows and c columns (1 ≤ r,c ≤ 600). Some of the cells contain walls (denoted by #, ASCII code 35), others are empty (denoted by ., ASCII code 46). There are two special empty cells: one starting point (denoted by S) and one treasure (denoted by T).
In each step the player may only move in one of the four cardinal directions. In other words, each two subsequent cells on his path have to share a common side. The treasure is always reachable from the starting point. The player is not allowed to leave the maze or enter a cell with a wall.
Mark’s task was to find the length of shortest path from the starting point to the treasure. He solved this task using breadth-first search (BFS).
His C++ solution is given in the input file. Below you can find the solution in pseudocode. However, Mark made a common bug in his implementation of the FIFO (first in, first out) queue – he is using a circular array of size k. Show him that his queue is too short!
Problem specification
Find a map of a maze such that if Mark’s program is executed on your maze, the queue size will exceed k at some moment. In the easy subproblem, k = 5000. In the hard subproblem, k = 15000. (The queue size is the number of cells it contains.) Your maze must satisfy all the constraints given above.
Input specification
The input file for this problem contains a reference C++ implementation of Mark’s solution. The variable size in this implementation must exceed k.
Output specification
On the first line output two integers separated by a single space: number of rows r and number of columns c. Then output r rows with c characters in each – the map of your maze.
Example