192. Knight's Move
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
This problem is worth 40 points.

You have an 8 by 8 chessboard with several knights on it. The chessboard has no other pieces on it. Given the positions of the knights, find all of the spaces that the knights can travel to in a single move.

Recall that in chess, a knight can move exactly 2 spaces in one direction, and exactly one space in a perpendicular direction. For example, a knight could move 2 spaces left and 1 space up, or 2 spaces up and 1 space left, but a knight could not move 2 spaces left on its own, or 1 space up and 1 space right, for example.

Input

The input consists of 8 lines, each consisting of 8 characters, representing the chessboard.

A single dot (".") represents an empty space on the chessboard, and an uppercase K ("K") represents the position of a knight.

Output

Output 8 lines, in the same format as the input, except, replace each empty space that can be moved to by at least one knight in a single move with an asterisk ("*").

Examples
Input
........
........
........
...K....
........
.....K..
........
........
Output
........
..*.*...
.*...*..
...K*.*.
.*.*.*.*
..*.*K..
...*...*
....*.*.
Input
........
..K....K
........
...K....
........
.....K..
........
......KK
Output
*...**..
..K.*..K
**..**..
.*.K*.*.
.*.*.*.*
..*.*K**
...***.*
....*.KK
Input
........
........
........
........
........
........
........
.......K
Output
........
........
........
........
........
......*.
.....*..
.......K