Grid Shading Puzzle

You want to solve a puzzle printed in a newspaper.

You are given a board divided into $n \times n$ unit squares. Each square may be shaded or left blank. For every row and every column you are told the exact number of squares that must be shaded.

Decide whether the board can be shaded so that all of the given per-row and per-column counts are satisfied.

The first line contains the number of test cases $t$ ($1 \le t \le 100$). The descriptions of the test cases follow.

The first line of each test case contains the board size $n$ ($1 \le n \le 100\,000$). The second line contains $n$ integers $w_1, w_2, \dots, w_n$ and the third line contains $n$ integers $k_1, k_2, \dots, k_n$ ($0 \le w_i, k_i \le n$). Here $w_i$ is the number of squares that must be shaded in row $i$, and $k_i$ is the number of squares that must be shaded in column $i$.

You may assume that the sum of $n$ over all test cases in a single input does not exceed $1\,500\,000$.

For each test case, print a single line containing TAK if the puzzle can be solved, or NIE otherwise.