Robot

Time limit1sMemory limit1024 MB

Summary

Build a grid maze of 0s and 1s, at most 1000 by 1000, so that exactly K right-or-down paths lead from the top-left to the bottom-right cell.

Level: Medium6 of 10
Topics: Math, Dynamic programming, Implementation
Solved: No attempts yet

Problem

Krešo likes to play with his robot. He builds a maze for the robot and then watches how the robot moves through it.

The robot starts in the top-left corner of the maze, which is a board with R rows and S columns. Some cells are blocked. At each step the robot can move to the cell on its right or the cell below it. If that cell is blocked, the robot cannot move there. The game ends when the robot reaches the bottom-right corner.

Krešo wants his maze to have exactly K different paths the robot can take during the game. Two paths are different if some cell is visited by one path and not by the other. Help Krešo build such a maze.

You may choose the dimensions yourself, but both R and S must be at most 1000. The top-left and bottom-right cells cannot be blocked.

Input

The first and only line contains a natural number K (1 ≤ K ≤ 1 000 000 000).

Output

Print the dimensions R and S of the maze on the first line (1 ≤ R, S ≤ 1 000).

Then print R lines, each with S characters '0' or '1'. A '1' marks a blocked cell and a '0' marks a free cell.

Hint

Explanation of the first test case: the maze below is one of the possible mazes that contain only one path, as described in the statement. The following solution is also possible.

Examples3

Example 1
Input
```
1
```
Expected output
```
3 3
000
110
110
```
Example 2
Input
```
2
```
Expected output
```
2 2
00
00
```
Example 3
Input
```
4
```
Expected output
```
5 5
00000
01110
01000
00000
01000
```