Not very black path

Limits: 3 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk has a connected graph with \(n\) vertices and \(m\) undirected edges. Each vertex is colored in one of two colors — white or black.

Marichka considers any path in this graph to be not very black if it contains no more than \(c\) consecutively visited black vertices. Note that a path can visit vertices more than once.

She prepared \(q\) queries for Zenyk. Each query consists of two white vertices \(x_i\) and \(y_i\), and a number \(k_i\), and Zenyk must determine whether there exists a not very black path from \(x_i\) to \(y_i\) with \(c = k_i\).

Your task is to help Zenyk find the answers to all of Marichka’s queries.

Input

The first line contains three integers \(n\), \(m\), and \(q\) — the number of vertices, edges, and queries respectively. The vertices are numbered with integers from 1 to \(n\) inclusive.

The next line contains a string of \(n\) characters without spaces, the \(i\)-th of which is equal to 0 if the corresponding vertex of the graph is white, or 1 — if it is black.

The next \(m\) lines describe the edges of the graph — pairs of numbers \(u_i\) and \(v_i\), separated by a space.

The next \(q\) lines describe the queries — triplets of numbers \(x_i\), \(y_i\), and \(k_i\), separated by a space.

Output

Output \(q\) lines, each containing the answer to the corresponding query: Tak, if a not very black path exists, or Ni — otherwise.

Constraints

\(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\) and \(y_i\) are white,

the given graph is connected.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 4 3 10000 1 3 5 1 4 2 2 1 2 5 0 4 2 0 4 3 1	Ni Tak Tak

Input (stdin) сopy	Output (stdout) сopy
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