Under construction

Still being built. Things may change

Building a Symmetric Stair

Time limit3sMemory limit512 MB

Summary
Given n unit cubes, build a symmetric stair (Ferrers diagram symmetric across the diagonal) using all n cubes, or report it is impossible.
Level

Medium5 of 10

Topics
Math, Implementation, Combinatorics, Greedy
Solved
No attempts yet

Problem

Little Barney just got a new set of toy cubes from his parents. The set contains nn identical cubes. Barney immediately started building various objects with these cubes.

The latest thing Barney built is a stair. A stair consists of one or more towers of cubes, where the heights of the towers are non-increasing from left to right. In the picture below, you can see three different shapes with 12 cubes each. The first two are stairs and the third one is not a stair.

Barney noticed that for some stairs you can turn your head 90 degrees to the right and you will see the same stair, but reversed! He calls such stairs symmetric. For example, the first stair above is symmetric, but the second one is not. Formally, a stair is symmetric if and only if reflecting the picture over the line x=yx = y gives the same stair, where the xx-axis is horizontal and oriented to the right, and the yy-axis is vertical and oriented upwards.

Barney wants to build a symmetric stair using all of his nn cubes. Show him how to do it!

Input

The single line of the input contains an integer nn, the number of cubes at Barney's disposal. (1≤n≤1001 \le n \le 100)

Output

If there is no symmetric stair with nn cubes, output a single integer −1-1.

Otherwise, in the first line, output one integer mm, the number of rows and columns in the picture of the stair. (1≤m≤1001 \le m \le 100) Then output mm lines describing the stair. Each line must contain exactly mm characters, each of which is the lowercase English letter ‘o’ or ‘.’. Here ‘o’ describes a cell with a cube, and ‘.’ describes an empty cell. There must be exactly nn ‘o’ characters in total. The cell in the bottom left corner must contain a cube. If there is more than one solution, output any of them.

Examples2

  1. Example 1

    Input
    3
    
    Expected output
    3
    ...
    o..
    oo.
    
  2. Example 2

    Input
    17
    
    Expected output
    5
    o....
    ooo..
    oooo.
    oooo.
    ooooo