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

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