Byteland Worldbeat Publishers

Byteasar is a manager at Byteland Worldbeat Publishers (BWP), which employs $n$ composers and $m$ lyricists. The artists work in pairs, each pair made of exactly one composer and one lyricist.

Byteasar knows every employee's skills, so he can estimate how productive any composer-lyricist pair would be. The efficiency of a pair is the number of songs it writes per week.

Byteasar wants to form $\min(n, m)$ disjoint pairs (every artist belongs to at most one pair) so that the total number of songs per week is as large as possible. Artists left without a partner do not work.

After studying the data, Byteasar suspects that the weekly total does not depend on how the pairs are chosen. Help him check this suspicion: decide whether every way of forming $\min(n, m)$ disjoint pairs yields the same total efficiency.

The first line contains one integer $t$ ($1 \le t \le 10$), the number of test cases. The test cases follow.

Each test case begins with a line of three integers $n$, $m$, and $k$ ($1 \le n, m \le 100000$, $1 \le k \le 300000$): the number of composers, the number of lyricists, and the number of description lines. Composers are numbered $1$ to $n$ and lyricists $1$ to $m$.

Each of the next $k$ lines contains four integers $a_i$, $b_i$, $c_i$, and $p_i$ ($1 \le a_i \le n$, $1 \le b_i \le c_i \le m$, $1 \le p_i \le 10^9$): composer $a_i$ together with any lyricist from $b_i$ to $c_i$ (inclusive) produces $p_i$ songs per week.

Each composer-lyricist pair is described at most once. A pair that is not listed has efficiency $0$ songs per week, yet it may still be formed.

For each test case print one line: TAK (Polish for "yes") if every arrangement of $\min(n, m)$ disjoint pairs gives the same total efficiency, or NIE (Polish for "no") otherwise.