Кольорове намисто

Обмеження: 3 сек., 512 МіБ

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

Хлопець хоче, щоб у намисті було $n$ намистинок розташованих в ряд. Відстань між кожною парою сусідніх намистинок повинна бути 1 см. Звісно ж, намистинки повинні бути кольоровими.

Також Зеник знає, що Марічка буде щаслива, якщо для $i$-ої намистинки найближча намистинка такого ж кольору буде на відстані рівно $d_i$ см. Якщо більше намистинок такого ж кольору не повинно існувати, то $d_i=0$. Правда, Марічку цікавлять не всі намистинки. Для деяких намистинок $d_i=-1$, а це означає, що не важливо, де знаходиться найближча намистинка такого ж кольору. Допоможіть Зенику перевірити, чи зможе він зробити таке намисто.

Вхідні дані

У першому рядку задано єдине число $n$ — кількість намистинок в намисті.

У другому рядку задано $n$ цілих чисел $d_i$. Якщо $d_i=0$, то більше не повинно бути намистинок такого ж кольору. Якщо $d_i=-1$, то неважливо чи існує намистинка такого ж кольору та на якій вона відстані.

Вихідні дані

Виведіть TAK, якщо існує таке намисто, що подобається Марічці, та NI, якщо не існує.

Якщо намисто існує, виведіть в другому рядку $n$ чисел $C_i$ — кольори відповідних намистинок. Усі кольори повинні бути цілими числами від 1 до $10^9$. Якщо існує декілька можливих варіантів відповіді, виведіть будь-який із них.

Обмеження

$2 \le n \le 3 \cdot 10^5$,

$-1 \le d_i \le n - 1$.

Приклади