Illuminated Triangular Pattern

Aya is studying decorative patterns made of colored lights. A triangular pattern with (n) levels consists of (n) rows. The (i)-th row contains (2\times i-1) '#' characters forming an isosceles triangle. To add some fun, Aya replaces every '#' whose position (1-indexed) in the row is a perfect square (i.e. (1, 4, 9, \dots)) with a '!'.

For example, a 3-level pattern is constructed as follows:

Original pattern:

  #

#####</pre>
After replacing, the pattern becomes:

  !
!##
!##!#

Given a positive integer (n), output the final pattern.

inputFormat

A single positive integer (n) representing the level of the pattern.

outputFormat

Print the final pattern containing (n) rows. Each row should be center-aligned with leading spaces such that the last row has no leading spaces. In each row, replace the characters at positions that are perfect squares with '!' and keep the rest as '#' characters.

sample

1

!