Good Sequence

Time limit1sMemory limit128 MB

Summary
Construct the lexicographically smallest square-free string of length N over the alphabet {1,2,3} (no two adjacent equal-length substrings identical).
Level

Medium6 of 10

Topics
Greedy, String, Backtracking
Solved
No attempts yet

Problem

Consider sequences made only of the digits 1, 2, and 3. If, for some positive length, two adjacent subsequences of that length are identical, the sequence is bad. If no such pair exists, the sequence is good.

The following sequences are bad.

  • 33
  • 32121323 (21 repeats immediately)
  • 123123213 (123 repeats immediately)

The following sequences are good.

  • 2
  • 32
  • 32123
  • 1232123

Among all good sequences of length N, treat each sequence as an N-digit integer and find the sequence representing the smallest value. For instance, 1213121 and 2123212 are both good sequences, but the smaller one is 1213121.

Input

The input consists of one integer N. N is between 1 and 80, inclusive.

Output

Print the sequence representing the smallest value among all good sequences of length N made only of 1, 2, and 3. Do not print spaces between digits.

Examples1

  1. Example 1

    Input
    7
    Expected output
    1213121