Не дуже чорний шлях

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

У Зеника є зв’язний граф із \(n\) вершин та \(m\) неорієнтованих ребер. Кожна вершина пофарбована у один із двох кольорів — білий або чорний.

Марічка вважає довільний шлях у цьому графі не дуже чорним, якщо у ньому немає більше ніж \(c\) підряд відвіданих чорних вершин. Зауважте, що шлях може відвідувати вершини більше ніж один раз.

Вона підготувала Зенику \(q\) запитів. Кожен запит — це дві білі вершини \(x_i\) та \(y_i\), а також число \(k_i\), і Зеник має визначити, чи існує не дуже чорний шлях від \(x_i\) до \(y_i\) при \(c = k_i\).

Ваше завдання — допомогти Зенику знайти відповіді на усі запити Марічки.

Вхідні дані

У першому рядку задано три цілі числа \(n\), \(m\) та \(q\) — кількість вершин, ребер та запитів відповідно. Вершини пронумеровані цілими числами від 1 до \(n\) включно.

У наступному рядку задано рядок із \(n\) символів без пробілів, \(i\)-й з яких рівний 0, якщо відповідна вершина графу біла, або 1 — якщо чорна.

У наступних \(m\) рядках задано ребра графу — пари чисел \(u_i\) та \(v_i\), розділені пробілом.

У наступних \(q\) рядках задано запити — трійки чисел \(x_i\), \(y_i\) та \(k_i\), розділені пробілом.

Вихідні дані

Виведіть \(q\) рядків, кожен з яких містить відповідь на відповідний запит: Tak, якщо не дуже чорний шлях існує, або Ni — якщо ні.

Обмеження

\(2 \le n \le 5 \cdot 10^5\),

\(0 \le m, k_i \le 5 \cdot 10^5\),

\(1 \le q \le 5 \cdot 10^5\),

\(1 \le u_i, v_i, x_i, y_i \le n\),

\(u_i \ne v_i\),

\(x_i\) та \(y_i\) — білі,

заданий граф — зв’язний.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 4 3 10000 1 3 5 1 4 2 2 1 2 5 0 4 2 0 4 3 1	Ni Tak Tak

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
11 12 6 10111100101 2 1 2 3 3 4 1 4 4 8 9 4 9 10 1 5 6 5 6 7 6 11 7 11 2 7 2 2 7 3 10 8 2 2 8 1 2 10 2 10 7 2	Ni Tak Tak Ni Tak Ni