#P3537. [POI2012] SZA-Cloakroom

[POI2012] SZA-Cloakroom


The annual rich citizen's reunion is taking place in Byteotia.

They meet to boast about their incomes, Lebytene's shoes and other luxuries.

Naturally, not all these objects of pride are carried into the banquet - coats, jackets, umbrellas and such are left in the cloakroom, and picked up upon leave.

Unfortunately for the well off, a gang of Byteotian thieves plans to break into the cloakroom and steal part of the items stored therein.

At this very moment the gang's leader is examining the plans of the robbery put forward by other gang members (they are a democratic lot!).

A plan typically looks as follows: the thieves break into the cloakroom at time mjm_j, take items worth exactly kjk_j and escape, where the whole heist takes them sjs_j time.

The gang leader would first of all like to know which of these plans are feasible and which are not.

A plan is feasible if at time mjm_j it is possible to collect items of total value kjk_j in such a way that up to the very mj+sjm_j+s_j moment no one shows up to retrieve any of the stolen goods (in such event, they would notify security, and the robbery would fail).

In particular, if at time mjm_j it is impossible to select items of exact total worth kjk_j, then the plan is infeasible and consequently rejected.

Knowing the drop off and retrieval times for each item, determine which plans are feasible and which are not.

We assume that an item left in the cloakroom the moment a robbery starts can already be stolen (see the example).


In the first line of the standard input there is a single integer nn(1n1 0001\le n\le 1\ 000) denoting the number of items that will be left in the cloakroom.

Those items are described in the nn lines that follow.

Each of those lines consists of three integers cic_i, aia_i, and bib_i (1ci1 0001\le c_i\le 1\ 000, 1ai<bi1091\le a_i<b_i\le 10^9), separated by single spaces, that denote respectively: the item's value, the moment it is left in the cloakroom, and the moment it will be retrieved by the owner.

The next line holds an integer pp (1p1 000 0001\le p\le 1\ 000\ 000),the number of plans the gang came up with. Each is specified in a separate line by three integers,mjm_j,kjk_j and sjs_j(1mj1091\le m_j\le 10^9,1kj100 0001\le k_j\le 100\ 000,0sj1090\le s_j\le 10^9), separated by single spaces, that denote respectively: the moment the thieves would enter the cloakroom, the value of goods they would like to steal, and the time the robbery would take them.

In test worth 16% of the total points p10p\le 10 holds in addition.

n some other tests, also worth 16% of the points, all the items have the same aia_i values.

In yet other tests, worth 24% of the points, all the queries share the same sjs_j value.


For each plan put forward by the gang determine if it is feasible, i.e., whether it is possible to steal items of total worth exactly kjk_j and escape before anyone asks for their belongings.

If the plan is feasible, your program should print the word TAK (Polish for yes) on the standard output, otherwise it should print NIE (Polish for no).


nn 件物品,每件物品有三个属性 ai,bi,ci (ai<bi)a_i, b_i, c_i\ (a_i<b_i)。注意输入顺序为 ci,ai,bic_i, a_i, b_i

再给出 qq 个询问,每个询问由非负整数 m,k,sm, k, s 组成,问是否能够选出某些物品使得:

  1. 对于每个选的物品 ii,满足 aima_i\le mbi>m+sb_i>m+s
  2. 所有选出物品的 cic_i 的和正好是 kk
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5