题目描述

译自 POI 2012 Stage 2. Day 1「Szatnia」

富人们聚会时把一些东西留在了衣帽间，而一群盗贼正准备盗取衣帽间内的物品。衣帽间有 $n$ 件物品，有 $p$ 条盗窃计划有这样的形式：盗贼们在 $m_j$ 时间闯入聚会现场，在 $s_j$ 的时间内偷走价值总和恰好为 $k_j$ 的物品并逃离。

你需要判断这些盗窃计划是否可行，也就是是否能在 $m_j$ 到 $m_j+s_j$ 这段时间内偷走价值总和恰好为 $k_j$ 的物品，且没有人在这段时间取回这些物品（如果有人发现自己的东西丢了，盗贼们就会被发现）。

输入格式

第一行一个整数 $n (1 \le n \le 1\ 000)$，表示物品的个数。

接下来 $n$ 行每行三个整数 $c_i, a_i, b_i (1 \le c_i \le 1\ 000,1 \lt a_i \lt b_i \le 10^9)$，表示物品的价值，和其放入衣帽间、取回的时间。

接下来一行一个整数 $p (1 \le p \le 1\ 000\ 000)$，表示盗窃计划数。

接下来 $p$ 行每行三个整数 $m_j, k_j, s_j (1 \le m_j \le 10^9,1 \le k_j \le 100\ 000,0 \le s_j \le 10^9)$，表示一次盗窃计划。

输出格式

对每次盗窃计划输出一行 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

数据范围与提示

对于 $16\%$ 的测试数据，保证 $p \le 10$.

对于另外 $16\%$ 的测试数据，所有物品的 $a_i$ 相同。

对于另外 $24\%$ 的测试数据，所有询问的 $s_j$ 相同。

对于所有测试数据，$1 \le n \le 1\ 000,1 \le c_i \le 1\ 000,1 \lt a_i \lt b_i \le 10^9,1 \le m_j \le 10^9,1 \le k_j \le 100\ 000,0 \le s_j \le 10^9$.