Mutations

Byte geneticists have long studied the byteacid (bajtokwas) sequences of two model organisms: the nematode Bajtorhabditis elegans and the fruit fly Bajtophila melanogaster. To learn how much of the fly's sequence descends from the nematode's, they want to find as many identical fragments in the two sequences as possible. The work is complicated by the fact that, as the species evolved, mutations may have occurred: one kind of byteacid in a sequence could turn into another kind.

Kinds of byteacids are written as natural numbers. We assume that a single mutation applies at once to every occurrence of a given kind of byteacid within a sequence fragment. For example, the fragment 2 1 2 can turn, in one mutation, into 6 1 6, 2 5 2, or 2 2 2, but not into 2 1 6 or 1 1 2.

Your task is to help the geneticists answer questions of the form: could a given fragment of the fly sequence have arisen from a given fragment of the nematode sequence through at most one mutation?

The first line contains an integer $n$ ($2 \le n \le 500\,000$), the length of the nematode's byteacid sequence. The second line contains $n$ integers $u_i$ ($1 \le u_i \le 500\,000$), the kinds of the successive byteacids in the nematode's sequence. The third line contains an integer $m$ ($2 \le m \le 500\,000$), the length of the fly's byteacid sequence. The fourth line contains $m$ integers $v_i$ ($1 \le v_i \le 500\,000$), the kinds of the successive byteacids in the fly's sequence.

The fifth line contains an integer $q$ ($1 \le q \le 500\,000$), the number of queries. Then $q$ lines follow; each contains three integers $a_i$, $b_i$, and $l_i$ ($1 \le a_i \le a_i + l_i - 1 \le n$, $1 \le b_i \le b_i + l_i - 1 \le m$). Such a query asks whether the fragment $[b_i,\, b_i + l_i - 1]$ of the fly sequence could have arisen from the fragment $[a_i,\, a_i + l_i - 1]$ of the nematode sequence through at most one mutation. Both fragments have the same length $l_i$.

Print $q$ lines. The $i$-th line must contain a single word, TAK or NIE, giving the answer to the $i$-th query. TAK means yes (it is possible) and NIE means no (it is not).