E. Generalized Sierpiński Carpet
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Polish mathematician Wacław Sierpiński once designed a famous fractal known as the Sierpiński Carpet, a beautiful and infinitely complex pattern created by recursively removing parts of a square. But what if we could modify the removal pattern?

You have discovered a Generalized Sierpiński Carpet, where the recursion follows a custom $$$3 \times 3$$$ pattern $$$P$$$ consisting of the characters '*' and '.'. Your task is to generate and print this fractal for a given number of recursion steps.

Let's say that $$$S_n$$$ is the Generalized Sierpiński Carpet with $$$n$$$ recursive steps, we define $$$S_n$$$ as follows:

  • $$$S_0$$$ is a grid of size $$$1 \times 1$$$ consisting only of the character '*'.
  • $$$S_n$$$ is a grid of size $$$3^n \times 3^n$$$, built by replacing each '*' symbol with $$$S_{n-1}$$$, and each '.' with a grid of size $$$3^{n-1} \times 3^{n-1}$$$ filled with the character '.'.

Given $$$n$$$ and $$$P$$$, print $$$S_n$$$.

Input

The first line contains a single integer $$$n$$$ ($$$0 \leq n \leq 6$$$) – the number of recursive steps.

Each of the $$$3$$$ lines contains $$$3$$$ characters, where each character is either '*' or '.' – the description of $$$P$$$.

Output

Print $$$S_n$$$.

Examples
Input
2
***
*.*
***
Output
*********
*.**.**.*
*********
***...***
*.*...*.*
***...***
*********
*.**.**.*
*********
Input
2
*.*
.*.
*.*
Output
*.*...*.*
.*.....*.
*.*...*.*
...*.*...
....*....
...*.*...
*.*...*.*
.*.....*.
*.*...*.*
Input
1
*..
.*.
***
Output
*..
.*.
***