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

Обмеження: 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\).

Приклади