No tag edit access

D. Tournament Construction

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputIvan is reading a book about tournaments. He knows that a tournament is an oriented graph with exactly one oriented edge between each pair of vertices. The score of a vertex is the number of edges going outside this vertex.

Yesterday Ivan learned Landau's criterion: there is tournament with scores *d*_{1} ≤ *d*_{2} ≤ ... ≤ *d*_{n} if and only if for all 1 ≤ *k* < *n* and .

Now, Ivan wanna solve following problem: given a set of numbers *S* = {*a*_{1}, *a*_{2}, ..., *a*_{m}}, is there a tournament with given set of scores? I.e. is there tournament with sequence of scores *d*_{1}, *d*_{2}, ..., *d*_{n} such that if we remove duplicates in scores, we obtain the required set {*a*_{1}, *a*_{2}, ..., *a*_{m}}?

Find a tournament with minimum possible number of vertices.

Input

The first line contains a single integer *m* (1 ≤ *m* ≤ 31).

The next line contains *m* distinct integers *a*_{1}, *a*_{2}, ..., *a*_{m} (0 ≤ *a*_{i} ≤ 30) — elements of the set *S*. It is guaranteed that all elements of the set are distinct.

Output

If there are no such tournaments, print string "=(" (without quotes).

Otherwise, print an integer *n* — the number of vertices in the tournament.

Then print *n* lines with *n* characters — matrix of the tournament. The *j*-th element in the *i*-th row should be 1 if the edge between the *i*-th and the *j*-th vertices is oriented towards the *j*-th vertex, and 0 otherwise. The main diagonal should contain only zeros.

Examples

Input

2

1 2

Output

4

0011

1001

0100

0010

Input

2

0 3

Output

6

000111

100011

110001

011001

001101

000000

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/20/2019 07:09:04 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|