신호

시간 제한1초메모리 제한128 MB

요약

수열 s와 패턴 f가 주어질 때, f가 길이 a에서 b 사이인 정확히 k개의 조각 중 하나로 등장하는 가장 작은 시작 위치를 찾는다.

난이도: 보통10점 중 6점
유형: 문자열 매칭, 그리디, 누적 합
정답자: 아직 제출이 없습니다

문제

외계 지적 생명체를 찾는 프로젝트에서 우주로부터 받은 신호를 정수 수열로 기록했다. 원래 신호는 정수 $n$ 개로 이루어진 수열 $s$ 이다.

누군가 이 수열을 정확히 $k$ 개의 연속한 조각으로 잘랐는데, 어떤 조각도 너무 짧거나 너무 길지 않도록, 즉 모든 조각의 길이가 $a$ 이상 $b$ 이하가 되도록 잘랐다.

그런데 정수 $m$ 개로 이루어진 수상한 조각 $f$ 가 나타났다. 이 조각 $f$ 가 정말로 위와 같이 잘린 원래 수열 $s$ 의 한 조각일 수 있는지 판별하여라.

정확히 말하면, 수열 $s$ 를 각 길이가 $a$ 이상 $b$ 이하인 연속한 조각 정확히 $k$ 개로 나누되, 그 조각 중 하나가 $f$ 와 완전히 같아지도록(길이 $m$ 이 같고 값이 순서대로 모두 같음) 나눌 수 있는지를 판별하면 된다. 가능하다면 그 조각이 $s$ 에서 시작하는 위치(1부터 시작하는 번호)도 함께 구한다. 가능한 위치가 여러 개라면 가장 앞선(가장 작은) 위치를 답한다.

입력

첫째 줄에 테스트의 개수 $d$ ( $1 \le d \le 1000$ )가 주어지고, 이어서 각 테스트의 설명이 차례대로 주어진다.

각 테스트는 다음과 같이 주어진다.

첫째 줄: 원래 수열 $s$ 의 길이 $n$ ( $1 \le n \le 10^5$ )
둘째 줄: 원래 수열을 이루는 $n$ 개의 정수 $s_1, s_2, \dots, s_n$ ( $-10^9 \le s_i \le 10^9$ )
셋째 줄: 자르는 방법을 나타내는 세 정수 $a$ , $b$ , $k$ ( $1 \le a \le b \le n$ ; $1 \le k \le n$ ; $a \cdot k \le n \le b \cdot k$ )
넷째 줄: 수상한 조각의 길이 $m$ ( $a \le m \le b$ )
다섯째 줄: 수상한 조각 $f$ 를 이루는 $m$ 개의 정수 $f_1, f_2, \dots, f_m$ ( $-10^9 \le f_i \le 10^9$ )

출력

각 테스트마다 한 줄씩 출력한다. 수상한 조각 $f$ 가 원래 수열 $s$ 에서 나올 수 없다면 NIE를 출력한다. 나올 수 있다면 TAK를 출력하고, 한 칸 띄운 뒤 그 조각이 원래 수열에서 시작하는 위치(1부터 시작하는 번호)를 출력한다. 가능한 위치가 여러 개이면 가장 작은 위치를 출력한다.

출력 토큰 TAK(가능)와 NIE(불가능)는 정해진 문자열이므로 그대로 출력해야 한다.

예제3

예제 1

입력

3
6
1 2 3 4 5 6
1 3 3
2
2 3
6
1 2 3 4 5 6
2 3 3
2
2 3
6
7 3 3 3 4 2
2 3 3
2
3 3

예상 출력

TAK 2
NIE
TAK 3

예제 2
입력
```
1
5
1 2 3 4 5
1 2 3
2
9 9
```
예상 출력
```
NIE
```
예제 3
입력
```
1
4
5 5 5 5
1 2 2
2
5 5
```
예상 출력
```
TAK 1
```