Замок у вигляді міні-гри#4651

Замок у вигляді міні-гри

1 секунда

256 мегабайтів

Складна

У багатьох комп'ютерних іграх відмикання замків реалізовано у вигляді міні-ігор. Полікарп придумав для своєї гри міні-гру з такими правилами:

На екрані показано три невід'ємних числа $a$ , $b$ та $c$ , а також три кнопки з написами "a", "b" та "c".

Кнопка "a": збільшує $a$ на $1$ і зменшує $b$ та $c$ на $1$ . Цю кнопку можна натискати лише тоді, коли і $b$ , і $c$ більше $0$ .
Кнопка "b": збільшує $b$ на $1$ і зменшує $a$ та $c$ на $1$ . Цю кнопку можна натискати лише тоді, коли і $a$ , і $c$ більше $0$ .
Кнопка "c": збільшує $c$ на $1$ і зменшує $a$ та $b$ на $1$ . Цю кнопку можна натискати лише тоді, коли і $a$ , і $b$ більше $0$ .

Замок вважається відкритим, якщо після деякої (можливо, порожньої) послідовності натискань сума $a + b + c = 1$ a + b + c = 1.

Ваше завдання — визначити мінімальну кількість натискань, необхідних для відкриття замка, або встановити, що це неможливо. Якщо замок можна відкрити, виведіть будь-яку оптимальну послідовність натискань, що це здійснює.

Вхідні дані

У першому рядку записано три невід'ємних числа $a$ , $b$ , $c$ ( $0 \leq a, b, c \leq 1 0^{9}$ 0 \le a, b, c \le 10^9, $1 \leq a + b + c \leq 1 0^{9}$ 1 \le a + b + c \le 10^9) — початкові числа на екрані.

Вихідні дані

Виведіть одне число — мінімальну кількість натискань, необхідних для відкриття замка. Якщо відкрити замок неможливо, виведіть $- 1$ .

Якщо замок можна відкрити, то виведіть у другому рядку будь-яку оптимальну послідовність натискань — рядок, що складається лише з символів "a", "b", "c", "[", "]" та цифр. Цей рядок має задовольняти таку граматику (початковий символ answer):

character ::= a ∣ b ∣ c; sequence ::= character ∣ character sequence; block ::= character ∣ number [sequence]; answer ::= block ∣ block answer;

\begin{aligned} &\text{character} ::= \text{a} \mid \text{b} \mid \text{c}; \\ &\text{sequence} ::= \text{character} \mid \text{character} \ \text{sequence}; \\ &\text{block} ::= \text{character} \mid \text{number} [\ \text{sequence} \ ]; \\ &\text{answer} ::= \text{block} \mid \text{block} \ \text{answer}; \end{aligned}

Тут number ( $1 \leq$ number $< 1 0^{10}$ < 10^{10}) — додатне ціле число без початкових нулів.

Зверніть увагу, що правильний рядок відповідно до цієї граматики не повинен містити жодних пробілів.

Рядок виводу повинен кодувати послідовність натискань у оптимальному розв'язку. Блок character відповідає натисканню відповідної кнопки, а блок number [ sequence ] — повторенню цієї послідовності натискань number разів. Дивіться приклади для більшої наочності.

Приклади

Приклад

1 0 0
0

Приклад

1 2 2
2
ab

Приклад

5 1 5
-1

Приклад 1

Примітка

У першому прикладі замок вже відкритий, тож натискати кнопки не потрібно.

У другому прикладі послідовність "ab" (натиснути "a", потім "b") відкриває замок.

У третьому прикладі відкрити замок неможливо.