격자 색칠 수수께끼

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

요약

n x n 판의 각 행과 열에 칠할 칸 수가 주어질 때 조건을 만족하는 칠하기가 가능한지 판정한다.

난이도: 보통10점 중 4점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

신문에 실린 수수께끼를 풀려고 합니다.

$n \times n$ 개의 단위 정사각형으로 나뉜 판이 있습니다. 각 칸은 색칠하거나 비워 둘 수 있습니다. 각 행과 각 열마다 색칠해야 하는 칸의 정확한 개수가 주어집니다.

주어진 행별, 열별 개수를 모두 만족하도록 판을 색칠할 수 있는지 판별하세요.

입력

첫 줄에 테스트 케이스의 수 $t$ ( $1 \le t \le 100$ )가 주어집니다. 이어서 각 테스트 케이스의 정보가 주어집니다.

각 테스트 케이스의 첫 줄에는 판의 크기 $n$ ( $1 \le n \le 100\,000$ )이 주어집니다. 둘째 줄에는 $n$ 개의 정수 $w_1, w_2, \dots, w_n$ 이, 셋째 줄에는 $n$ 개의 정수 $k_1, k_2, \dots, k_n$ 이 주어집니다 ( $0 \le w_i, k_i \le n$ ). $w_i$ 는 $i$ 번째 행에서 색칠해야 하는 칸의 수이고, $k_i$ 는 $i$ 번째 열에서 색칠해야 하는 칸의 수입니다.

한 입력에 포함된 모든 테스트 케이스의 $n$ 값의 합은 $1\,500\,000$ 을 넘지 않습니다.

출력

각 테스트 케이스마다, 수수께끼를 풀 수 있으면 TAK을, 풀 수 없으면 NIE를 한 줄에 출력합니다.

예제2

예제 1
입력
```
2
3
1 2 3
3 2 1
3
1 3 0
2 2 0
```
예상 출력
```
TAK
NIE
```
예제 2
입력
```
2
2
2 0
1 1
2
2 0
2 0
```
예상 출력
```
TAK
NIE
```