[Poi2012]Cloakroom

有 $n$ 件物品，每件物品都有三个属性 $a_i$、$b_i$、$c_i$，且 $a_i<b_i$。

接下来给出 $q$ 个询问，每个询问由非负整数 $m$、$k$、$s$ 组成。对于每个询问，请判断能否选出若干件物品，使得：

1. 对于每件选出的物品 $i$，均满足 $a_i\le m$ 且 $b_i>m+s$；
2. 所有选出物品的 $c_i$ 之和恰好为 $k$。

输入格式

第一行包含一个正整数 $n$，表示物品数量。

接下来 $n$ 行，每行包含三个正整数 $c_i$、$a_i$、$b_i$，描述一件物品。

随后一行包含一个正整数 $q$，表示询问数量。

接下来 $q$ 行，每行包含三个非负整数 $m$、$k$、$s$，描述一个询问。

输出格式

输出 $q$ 行，第 $i$ 行对应第 $i$ 个询问的答案。

若能够选出满足条件的物品，则输出 TAK；否则输出 NIE。

样例输入

5

6 2 7

5 4 9

1 2 4

2 5 8

1 3 9

5

2 7 1

2 7 2

3 2 0

5 7 2

4 1 5

样例输出

TAK
NIE
TAK
TAK
NIE

数据范围

• $n\le 10^3$；
• $c_i\le 10^3$；
• $1\le a_i<b_i\le 10^9$；
• $q\le 10^6$；
• $1\le m\le 10^9$；
• $1\le k\le 10^5$；
• $0\le s\le 10^9$。

来源与许可

本题为 POI 2012 试题「Cloakroom」，题面与测试数据整理自 BZOJ。

样例 1

输入

5

6 2 7

5 4 9

1 2 4

2 5 8

1 3 9

5

2 7 1

2 7 2

3 2 0

5 7 2

4 1 5

输出

TAK
NIE
TAK
TAK
NIE