Recently, Vadim wrote his game, which he called “Cavalry Battle Advanced.” This game is somewhat reminiscent of chess but differs in some important aspects:

To prevent players from filling the entire available 3 × N board with knights, Vadim encoded a secret bonus. To understand it better, let’s imagine a graph where each placed knight is a vertex, and if a pair of knights can capture each other, there is an edge between the corresponding vertices in the graph. The bonus is added only if this graph is a tree (i.e., the graph is connected and acyclic).

It is clear that all professional players of “Cavalry Battle Advanced” want to both obtain this secret bonus and place the maximum possible number of knights on the designated board. Take on the role of these players and find such an arrangement.

A single line contains an integer N — the size of the board horizontally (1 ≤ N ≤ 10⁵).

Output the arrangement in the following format: 3 lines of N numbers 0 or 1 — 0 if the cell is empty, and 1 if there is a knight in the cell. Thus, you will get a table of size 3 × N. All knights must form a tree as described in the conditions.

If there are multiple suitable arrangements with the maximum number of knights, output any of them.