Problem Description

Input Format

The input is given from the standard input in the following format.

$ N $

Output Format

Output should be in the following format to the standard output.

$ H $ $ W $ $ S_1 $ $\vdots$ $ S_H $

Additionally, the following constraints must be satisfied.

• $H,\ W$ are integers satisfying $3\ \leq\ H,W\ \leq\ 32$
• $S_1,\ \ldots,\ S_H$ are strings consisting of #, ., S, G representing the grid map
• $\lvert\ S_i\rvert\ =\ W$
• All characters on the outermost part of the grid map are #
• There is exactly one S character in the grid map
• There is exactly one G character in the grid map
• The number of self-avoiding walks from S to G in the grid map is exactly $ N $

Sample Input and Output

Sample Input #1

2

Sample Output #1

4 4
####
#S.#
#.G#
####

Sample Input #2

8

Sample Output #2

5 9
#########
#S......#
#.#.#.#.#
#......G#
#########

Sample Input #3

184

Sample Output #3

6 6
######
#S...#
#....#
#....#
#...G#
######

Sample Input #4

1936

Sample Output #4

8 27
###########################
#.........................#
#.S####.#####.####...###..#
#...#.....#...#...#.#...#.#
#...#.....#...####..#.....#
#...#.....#...#.....#...G.#
#...#.....#...#......###..#
###########################

Notes/Hints

Problem Statement (One Line)

Output a grid map such that the number of self-avoiding walks (self-avoiding walk) from S to G is $ N $.

Problem Statement (Detailed)

Oneesan can solve the following problem quickly.

Given $ N,H,W $ and a grid map of height $ H $ and width $ W $ satisfying the following conditions:

• The grid map of height $ H $ and width $ W $ is represented by $ H $ strings of length $ W $, $S_1,\ S_2,\ \ldots,\ S_H$.
• Each cell is represented by one of the four characters: wall #, open space ., start S, and goal G.
• The outer perimeter is entirely made of walls #.
• There is exactly one start S and one goal G in the grid map.

On the grid map, a path from S to G is defined as a sequence of moves to adjacent cells (up, down, left, right) excluding walls #, including the start and goal cells. Two paths $P,\ Q$ are considered different if they have different lengths or there exists an $ i $ such that $P_i\ \ne\ Q_i$. A self-avoiding walk is a path that does not visit the same cell more than once. Determine the number of different self-avoiding walks in the given grid map and check if it equals $ N $. If it does, output Yes; otherwise, output No.

Oneesan enjoys counting self-avoiding walks using her abilities but finds generating grid maps herself boring. Therefore, she asks you to generate the grid map for her.

Given $ N $, output a grid map that would make Oneesan output Yes. Note that there are some limitations on the grid map due to Oneesan's specifications. Refer to the output section for details. It is guaranteed that a solution always exists under these constraints. Any solution that satisfies the constraints is acceptable.

Constraints

• $ N $ is an integer satisfying $0\ \leq\ N\ \leq\ 2{,}019$

Sample Explanation 1

There are other outputs that would also be correct.

见题面 Input 部分

见题面 Output 部分