Rating changes for last rounds are temporarily rolled back. They will be returned soon.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

dp

graphs

greedy

math

*2800

No tag edit access

The problem statement has recently been changed. View the changes.

×
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-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/27/2024 19:31:54 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|