Вам задан массив целых чисел \(a_1, a_2, \dots, a_n\), где \(a_i\) означает количество блоков на \(i\)-й позиции. Гарантируется, что \(1 \le a_i \le n\).
За одну операцию вы можете выбрать любое подмножество индексов и убрать один блок на каждой позиции в выбранном подмножестве. Вы не можете убрать блок с позиции, на которой уже нет блоков.
Все подмножества которые вы выбираете должны быть различными (уникальными).
Вам необходимо удалить все блоки за не более чем \(n+1\) операцию. Можно доказать, что ответ всегда существует.
Выходные данные
В первой строке выведите целое число \(op\) (\(0 \le op \le n+1\)).
В каждой из следующих \(op\) строк выведите бинарную строку \(s\) длины \(n\). Если \(s_i=\)'0', это означает, что позиция \(i\) не находится в выбранном подмножестве. Иначе, \(s_i\) должно быть равно '1', и позиция \(i\) находится в выбранном подмножестве.
Все строки должны быть различными и \(a_i\) должно быть равно сумме \(s_i\) по всем выбранным бинарным строкам.
Если есть несколько возможных ответов, вы можете вывести любой.
Гарантируется, что ответ существует.
Примечание
В первом примере количество блоков уменьшается следующим образом:
\(\lbrace 5,5,5,5,5 \rbrace \to \lbrace 4,4,4,4,4 \rbrace \to \lbrace 4,3,3,3,3 \rbrace \to \lbrace 3,3,2,2,2 \rbrace \to \lbrace 2,2,2,1,1 \rbrace \to \lbrace 1,1,1,1,0 \rbrace \to \lbrace 0,0,0,0,0 \rbrace\). Можно заметить, что все эти операции отличаются друг от друга.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 5 5 5 5
|
6
11111
01111
10111
11011
11101
11110
|
|
2
|
5
5 1 1 1 1
|
5
11000
10000
10100
10010
10001
|
|
3
|
5
4 1 5 3 4
|
5
11111
10111
10101
00111
10100
|