题目描述

译自 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 < a_i < 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 < a_i < 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$