题目描述

有 $n$ 件物品，每件物品有三个属性 $a_i,b_i,c_i$（$a_i<b_i$）。 再给出 $q$ 个询问，每个询问由非负整数 $m,k,s$ 组成，问是否能够选出某些物品使得：

1. 对于每个选的物品 $i$，满足 $a_i\leq m$ 且 $b_i>m+s$。
2. 所有选出物品的 $c_i$ 的和正好是 $k$。

输入格式

第一行一个整数 $n$。
接下来 $n$ 行每行三个整数，分别表示 $c_i,a_i,b_i$。
下面一行一个整数 $q$。
接下来 $q$ 行每行三个整数 $m,k,s$。

输出格式

输出 $q$ 行，每行为 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

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,c_i\leq 10^3$，$1\leq a_i<b_i\leq 10^9$，$1\leq m\leq 10^9$，$1\leq k\leq 10^5$，$1\leq q\leq 10^6$，$0\leq s\leq 10^9$。