Diameters

Limits: 4 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka have a tree: a set of \(n\) vertices and \(n-1\) edges such that any vertex can be reached from any other vertex by moving along the edges.

They also have \(m\) pairs of vertices \((a_i, b_i)\). Marichka sequentially removes vertices from the tree such that all non-removed vertices still form a tree, meaning each time the girl removes a leaf. A pair \((a_i, b_i)\) is considered successful if at some moment it was one of the diameters of the tree. That is, the distance between any pair of non-removed vertices is not greater than the distance from \(a_i\) to \(b_i\). If at some moment several different pairs are simultaneously diameters, then all of them are successful.

Zenyk has \(q\) queries, each of which is: can all pairs from the \(l\)-th to the \(r\)-th, i.e., the pairs \((a_l, b_l)\), \((a_{l+1}, b_{l+1})\), \(\dots\), \((a_r, b_r)\), be successful. Help Zenyk answer these queries.

Input

The first line contains a single integer \(n\).

The next \(n - 1\) lines contain 2 integers each, describing the edges of the tree.

The next line contains a single integer \(m\).

The next \(m\) lines contain 2 integers \(a_i\) and \(b_i\) each.

The next line contains a single integer \(q\).

The next \(q\) lines contain 2 integers \(l_i\) and \(r_i\) each.

Output

Output \(q\) lines. In the \(i\)-th line output TAK if it is possible for all pairs from \(l_i\) to \(r_i\) to be successful, and NI otherwise.

Constraints

\(1 \le n, m, q \le 2 \cdot 10^5\),

\(1 \le a_i, b_i \le n\), \(a_i \ne b_i\),

\(1 \le l_i \le r_i \le m\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 1 2 2 3 2 4 4 5 4 6 5 7 4 2 4 1 7 4 7 3 6 4 1 4 1 2 2 3 3 4	NI TAK TAK NI