Кольорове намисто
Limits: 3 sec., 512 MiB
Зеник хоче подарувати Марічці намисто. Але звісно ж подарунок буде особливим, якщо зробить його Зеник своїми руками.
Хлопець хоче, щоб у намисті було n намистинок розташованих в ряд. Відстань між кожною парою сусідніх намистинок повинна бути 1 см. Звісно ж, намистинки повинні бути кольоровими.
Також Зеник знає, що Марічка буде щаслива, якщо для i-ої намистинки найближча намистинка такого ж кольору буде на відстані рівно di см. Якщо більше намистинок такого ж кольору не повинно існувати, то di=0. Правда, Марічку цікавлять не всі намистинки. Для деяких намистинок di=−1, а це означає, що не важливо, де знаходиться найближча намистинка такого ж кольору. Допоможіть Зенику перевірити, чи зможе він зробити таке намисто.
Input
У першому рядку задано єдине число n — кількість намистинок в намисті.
У другому рядку задано n цілих чисел di. Якщо di=0, то більше не повинно бути намистинок такого ж кольору. Якщо di=−1, то неважливо чи існує намистинка такого ж кольору та на якій вона відстані.
Output
Виведіть TAK
, якщо існує таке намисто, що подобається
Марічці, та NI
, якщо не існує.
Якщо намисто існує, виведіть в другому рядку n чисел Ci — кольори відповідних намистинок. Усі кольори повинні бути цілими числами від 1 до 109. Якщо існує декілька можливих варіантів відповіді, виведіть будь-який із них.
Constraints
2≤n≤3⋅105,
−1≤di≤n−1.
Samples
Input (stdin) | Output (stdout) |
---|---|
7 3 1 1 2 0 2 -1 | TAK 4 47 47 4 7 4 47 |
Input (stdin) | Output (stdout) |
---|---|
3 1 1 2 | NI |