题目描述
译自 POI 2012 Stage 2. Day 1「Szatnia」
富人们聚会时把一些东西留在了衣帽间,而一群盗贼正准备盗取衣帽间内的物品。衣帽间有 n 件物品,有 p 条盗窃计划有这样的形式:盗贼们在 mj 时间闯入聚会现场,在 sj 的时间内偷走价值总和恰好为 kj 的物品并逃离。
你需要判断这些盗窃计划是否可行,也就是是否能在 mj 到 mj+sj 这段时间内偷走价值总和恰好为 kj 的物品,且没有人在这段时间取回这些物品(如果有人发现自己的东西丢了,盗贼们就会被发现)。
输入格式
第一行一个整数 n(1≤n≤1 000),表示物品的个数。
接下来 n 行每行三个整数 ci,ai,bi(1≤ci≤1 000,1<ai<bi≤109),表示物品的价值,和其放入衣帽间、取回的时间。
接下来一行一个整数 p(1≤p≤1 000 000),表示盗窃计划数。
接下来 p 行每行三个整数 mj,kj,sj(1≤mj≤109,1≤kj≤100 000,0≤sj≤109),表示一次盗窃计划。
输出格式
对每次盗窃计划输出一行 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≤10.
对于另外 16% 的测试数据,所有物品的 ai 相同。
对于另外 24% 的测试数据,所有询问的 sj 相同。
对于所有测试数据,1≤n≤1 000,1≤ci≤1 000,1<ai<bi≤109,1≤mj≤109,1≤kj≤100 000,0≤sj≤109.