Byteasar is a manager in Byteland Worldbeat Publishers (BWP). There are $n$ composers and $m$ lyricists employed there. The artists work in pairs consisting of one composer and one lyricist.

Byteasar knows the skills of BWP employees. Thus he can assess how effective a composer-lyricist pair is going to be. The efficiency of each potential pair is measured as the number of songs written per week.

Byteasar wants to arrange the employees in $\min(n, m)$ disjoint pairs such that the number of songs produced is as high as possible. Unpaired artists will not work.

After the analysis of the whole data Byteasar suspects that the total number of songs produced in BWP during a week is independent of the paring. Byteasar is surprised, therefore he asks you to write a program to verify this observation.

Input Format

The first line of input contains one integer $t$ ($1 ≤ t ≤ 10$), i.e., the number of test cases that follow.

Each test case starts with a line with three integers $n$, $m$ and $k$ ($1 ≤ n, m ≤ 100\,000$, $1 ≤ k ≤ 300\,000$) that are the number of composers, the number of lyricists and the number of lines describing the efficiency of pairs. Composers are numbered from 1 to n, while lyricists are numbered from $1$ to $m$.

Each of the next $k$ subsequent lines contains four integers $a_{i}$, $b_{i}$, $c_{i}$ and $p_{i}$ ($1 ≤ a_{i} ≤ n$, $1 ≤ b_{i} ≤ c_{i} ≤ m$, $1 ≤ p_{i} ≤ 10^{9}$) with the meaning that a pair of composer $a_{i}$ and any lyricist from the range $b_{i}$ to $c_{i}$ (inclusive) will produce $p_{i}$ songs per week.

Each composer-lyricist pair will be described at most once. If a pair is not mentioned in the input, its members will be assumed to be skilled in incompatible music genres, thus the efficiency of their work will be 0 songs a week. Nevertheless such a pair can be formed in BWP.

Output Format

Your program should output t lines with answers for subsequent test cases. For each test case the answer is TAK (i.e., yes in Polish) if for each arrangement of $\min(n, m)$ pairs, the total efficiency is the same. Otherwise, the answer is NIE (no in Polish).

Example

Input

2
2 3 3
1 1 3 3
2 1 1 3
2 2 3 3
3 3 7
1 1 1 5
1 2 2 6
2 1 1 5
2 2 2 6
3 1 1 8
3 2 2 9
3 3 3 10

Output

TAK
NIE