#P18367. Furniture

Furniture

Furniture

题目描述

Bajtazar 为公寓订购了 NN 件家具,想把它们全部放进一个大小为 A×BA\times B 的矩形客厅。第 ii 件家具是一个大小为 ci×dic_i\times d_i 的矩形。

每件家具都必须靠着两面长度为 AA 的墙中的某一面摆放,并且必须让长度为 cic_i 的边紧贴这面墙。也就是说,沿墙方向占用 cic_i,向房间内部延伸 did_i,不能改为让长度为 did_i 的边贴墙。

所有家具必须完全位于客厅内部。任意两件家具不能有面积为正的重叠,但可以沿边接触,也可以只在角点接触。

判断能否摆下所有家具。你需要处理 TT 组独立测试数据。

输入格式

第一行一个整数 TT,表示测试数据组数。

每组数据第一行三个整数 A,B,NA,B,N,分别表示客厅的尺寸和家具件数。

接下来 NN 行,第 ii 行两个整数 ci,dic_i,d_i,表示第 ii 件家具的尺寸。

输出格式

输出 TT 行。对于每组数据,若能摆下全部家具,输出 TAK;否则输出 NIE。

数据范围

  • 1≤T≤301\le T\le30。
  • 1≤A,B≤1061\le A,B\le10^6。
  • 1≤N≤10001\le N\le1000。
  • 1≤ci≤A1\le c_i\le A,1≤di≤B1\le d_i\le B。
  • 一个输入文件中,所有测试数据的 NN 之和不超过 10001000。

样例输入 1

4
9 7 6
2 2
3 2
4 5
1 5
1 3
6 2
3 3 3
3 1
1 1
3 1
3 3 3
1 3
1 3
1 3
3 3 2
2 2
2 2

样例输出 1

TAK
NIE
TAK
NIE

样例解释

第一组数据的一种合法摆放方式如下。图中每个小格的边长为 1,客厅宽 9、高 7;家具均以长度为 cic_i 的边贴着上墙或下墙。

第一组样例的一种合法摆放方式