Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Fox and Minimal path

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputFox Ciel wants to write a task for a programming contest. The task is: "You are given a simple undirected graph with *n* vertexes. Each its edge has unit length. You should calculate the number of shortest paths between vertex 1 and vertex 2."

Same with some writers, she wants to make an example with some certain output: for example, her birthday or the number of her boyfriend. Can you help her to make a test case with answer equal exactly to *k*?

Input

The first line contains a single integer *k* (1 ≤ *k* ≤ 10^{9}).

Output

You should output a graph *G* with *n* vertexes (2 ≤ *n* ≤ 1000). There must be exactly *k* shortest paths between vertex 1 and vertex 2 of the graph.

The first line must contain an integer *n*. Then adjacency matrix *G* with *n* rows and *n* columns must follow. Each element of the matrix must be 'N' or 'Y'. If *G*_{ij} is 'Y', then graph *G* has a edge connecting vertex *i* and vertex *j*. Consider the graph vertexes are numbered from 1 to *n*.

The graph must be undirected and simple: *G*_{ii} = 'N' and *G*_{ij} = *G*_{ji} must hold. And there must be at least one path between vertex 1 and vertex 2. It's guaranteed that the answer exists. If there multiple correct answers, you can output any of them.

Examples

Input

2

Output

4

NNYY

NNYY

YYNN

YYNN

Input

9

Output

8

NNYYYNNN

NNNNNYYY

YNNNNYYY

YNNNNYYY

YNNNNYYY

NYYYYNNN

NYYYYNNN

NYYYYNNN

Input

1

Output

2

NY

YN

Note

In first example, there are 2 shortest paths: 1-3-2 and 1-4-2.

In second example, there are 9 shortest paths: 1-3-6-2, 1-3-7-2, 1-3-8-2, 1-4-6-2, 1-4-7-2, 1-4-8-2, 1-5-6-2, 1-5-7-2, 1-5-8-2.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2022 16:50:57 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|