As you may remember,
a binary de Bruijn sequence of order *n* is a cyclic sequence of zeros and
ones such that every possible subsequence of *n* consecutive digits appears
exactly once.

Regarding the problem about de Bruijn sequences of the last UPC semifinal, Masao did not like that some precomputed solutions were accepted. In the good old days, when men were real men, and Masao was a UPC world-finalist of the ACM contest (and a real man, like now), things were not so easy! Therefore, let us make that problem a little tougher.

**Input**

Input consists of several cases.
Every case begins with an integer number *n*,
followed by a number *r*, followed by *r* restrictions,
each consisting of a pair of integer numbers *i* and *v*,
which state that the *i*-th leftmost position of the sequence must be *v*.
Assume 2 ≤ *n* ≤ 20, 0 ≤ *i* < 2^{n} and *v* ∈ {0, 1}.
The positions are all different.

**Output**

For every case,
print the lexicographically smallest de Bruijn sequence of order *n*
that fulfills all the restrictions.
If such a sequence does not exists, state so as shown in the sample output.

**Observation**

The private test cases are chosen so that a “reasonable” brute-force algorithm should be accepted, if written non-recursively.

Public test cases

**Input**

3 0 3 1 0 1 2 2 0 1 2 1 4 5 3 1 11 0 9 1 15 0 6 0

**Output**

00010111 10001011 no solution 0011010111100100

Information

- Author
- Xavier Martínez
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Vuitè Concurs de Programació de la UPC - Final
- Date
- 2010-09-22