8288번 - Byteland Worldbeat Publishers 다국어

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.

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⁹) 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.

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).