Гнучкі відрізки#8715

Гнучкі відрізки

1 секунда

128 мегабайтів

Дуже легка

Великий математик Володимир Германович помітив цікаву властивість деяких відрізків додатних цілих чисел, досліджуючи їх у пошуках нових закономірностей.

Володимир називає відрізок додатних цілих чисел $l, l + 1, \dots, r$ l, l + 1, \ldots, r гнучким, якщо він може змінити кожне число цього відрізка рівно на одиницю так, щоб добуток чисел на цьому відрізку не змінився. Тобто, існує послідовність $a_{l}, a_{l + 1}, \dots, a_{r}$ a_l, a_{l+1}, \ldots, a_r з наступними властивостями:

$a_{k} = k \pm 1$ a_k = k \pm 1
$l \cdot (l + 1) \cdot \dots \cdot r = a_{l} \cdot a_{l + 1} \cdot \dots \cdot a_{r}$ l \cdot (l + 1) \cdot \ldots \cdot r = a_l \cdot a_{l+1} \cdot \ldots \cdot a_r

Тепер Володимир Германович хоче дізнатися, чи може він побудувати гнучкий відрізок будь-якої довжини. За заданим додатним цілим числом $n$ знайдіть будь-який гнучкий відрізок, що складається з $n$ послідовних додатних цілих чисел, або повідомте, що такого відрізка не існує.

Вхідні дані

Одне ціле число $n$ ( $1 \leq n \leq 10000$ 1 \le n \le 10\,000) — довжина потрібного відрізка.

Вихідні дані

У першому рядку має бути "YES", якщо існує гнучкий відрізок з $n$ додатних цілих чисел. Інакше виведіть "NO".

Якщо такий відрізок існує, другий і третій рядки мають містити опис цього відрізка.

У другому рядку — єдине число $l$ ( $1 \leq l \leq 1000000$ 1 \le l \le 1\,000\,000) — перший елемент цього відрізка. Гарантується, що якщо гнучкий відрізок довжини $n$ існує, то існує і відрізок $[l, r]$ [l, r] довжини $n$ , такий що $1 \leq l \leq 1000000$ 1 \le l \le 1\,000\,000.

У третьому рядку — рядок довжини $n$ без пробілів. Він має складатися тільки з символів "+" та "-", де $(k - l + 1)$ (k - l + 1)-й символ цього рядка дорівнює "-", якщо $a_{k} = k - 1$ a_k = k - 1, або "+", якщо $a_{k} = k + 1$ a_k = k + 1.

Приклади

Приклад 1

Приклад 2

Примітка

У другому прикладі $n = 4$ n = 4, $l = 2$ l = 2, $r = l + n - 1 = 5$ r = l + n - 1 = 5. Відповідь така: $a_{2} = 2 - 1 = 1$ a_2 = 2 - 1 = 1, $a_{3} = 3 + 1 = 4$ a_3 = 3 + 1 = 4, $a_{4} = 4 + 1 = 5$ a_4 = 4 + 1 = 5, $a_{5} = 5 + 1 = 6$ a_5 = 5 + 1 = 6. Добуток чисел від $l$ до $r$ — $2 \cdot 3 \cdot 4 \cdot 5 = 120$ 2 \cdot 3 \cdot 4 \cdot 5 = 120. Добуток $a_{k}$ a_k — $a_{2} \cdot a_{3} \cdot a_{4} \cdot a_{5} = 1 \cdot 4 \cdot 5 \cdot 6 = 120$ a_2 \cdot a_3 \cdot a_4 \cdot a_5 = 1 \cdot 4 \cdot 5 \cdot 6 = 120. Отже, відрізок $[2, 5]$ — гнучкий.