Equal Adjacent Pair Occurrences in a Binary String

Given a positive integer \(n\), construct a binary string (i.e. a string that contains only the digits 0 and 1) of length \(n\) such that every one of the substrings \(01\), \(00\), \(10\), and \(11\) appears an equal number of times as contiguous segments. If no such string exists, output No solution.

For example, in the string 1011101 the substrings are counted over all consecutive positions. Here, the occurrences are: 01 appears 2 times, 00 appears 0 times, 10 appears 2 times, and 11 appears 2 times. These counts are not all equal.

Note: The occurrence of a pair is defined as appearing exactly as a contiguous substring in the original string. Also, for large test cases the input-output samples include one big sample directly in the sample cases.

Hint: For a string of length \(n\) with \(n\ge2\), there are \(n-1\) adjacent pairs. Hence a necessary condition is that \(n-1\) must be divisible by 4. In the trivial case \(n=1\), no pair exists and the condition is satisfied.

A standard approach to construct a valid string for \(n\ge2\) (when possible) is to notice that the four distinct pairs \(00, 01, 10, 11\) can be viewed as the directed edges of a graph on vertices \(\{0,1\}\). If we require that each edge is used exactly \(t\) times, where \(t = \frac{n-1}{4}\), then an Eulerian circuit in this multigraph yields a solution.

If no Eulerian circuit exists (or the necessary divisibility condition is not met), output No solution.

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10^6\)).

Note: When \(n = 1\), the single-digit string trivially satisfies the condition. When \(n \ge 2\) the necessary condition is that \(n - 1\) is divisible by 4.

outputFormat

If a valid binary string exists, output one such string. Otherwise, output No solution.

sample

1

0