돌연변이

바이트 유전학자들은 오랫동안 두 모델 생물, 즉 선충 Bajtorhabditis elegans 와 초파리 Bajtophila melanogaster 의 바이트산(bajtokwas) 서열을 연구해 왔습니다. 초파리의 서열이 선충의 서열에서 얼마나 유래했는지 알아내기 위해, 이들은 두 서열에서 서로 같은 조각을 최대한 많이 찾고자 합니다. 그런데 종이 진화하는 과정에서 서열에 돌연변이가 일어났을 수 있어 연구가 까다롭습니다. 돌연변이란 서열 안의 어떤 한 종류의 바이트산이 다른 종류로 바뀌는 것을 말합니다.

바이트산의 종류는 자연수로 나타냅니다. 하나의 돌연변이는 서열 조각 안에서 해당 종류의 바이트산이 나타나는 모든 위치에 동시에 적용된다고 가정합니다. 예를 들어 조각 2 1 2 는 한 번의 돌연변이로 6 1 6, 2 5 2, 2 2 2 로는 바뀔 수 있지만 2 1 6 이나 1 1 2 로는 바뀔 수 없습니다.

여러분이 할 일은, 주어진 초파리 서열 조각이 주어진 선충 서열 조각으로부터 최대 한 번의 돌연변이로 만들어질 수 있는지를 묻는 질문들에 답하는 것입니다.

첫째 줄에는 선충 바이트산 서열의 길이를 나타내는 정수 $n$ ($2 \le n \le 500\,000$) 이 주어집니다. 둘째 줄에는 선충 서열을 이루는 각 바이트산의 종류를 나타내는 $n$ 개의 정수 $u_i$ ($1 \le u_i \le 500\,000$) 가 주어집니다. 셋째 줄에는 초파리 바이트산 서열의 길이를 나타내는 정수 $m$ ($2 \le m \le 500\,000$) 이 주어집니다. 넷째 줄에는 초파리 서열을 이루는 각 바이트산의 종류를 나타내는 $m$ 개의 정수 $v_i$ ($1 \le v_i \le 500\,000$) 가 주어집니다.

다섯째 줄에는 질문의 개수를 나타내는 정수 $q$ ($1 \le q \le 500\,000$) 가 주어집니다. 이어서 $q$ 개의 줄이 주어지며, 각 줄에는 세 정수 $a_i$, $b_i$, $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$) 가 주어집니다. 이는 초파리 서열의 조각 $[b_i,\, b_i + l_i - 1]$ 이 선충 서열의 조각 $[a_i,\, a_i + l_i - 1]$ 로부터 최대 한 번의 돌연변이로 만들어질 수 있는지를 묻는 질문입니다. 두 조각의 길이는 모두 $l_i$ 로 같습니다.

각 질문에 대해 한 줄씩, 총 $q$ 개의 줄을 출력합니다. $i$ 번째 줄에는 $i$ 번째 질문의 답을 나타내는 한 단어 TAK 또는 NIE 를 출력합니다. TAK 는 가능하다(예)를, NIE 는 불가능하다(아니오)를 뜻합니다.