18360번 - Logistics 다국어

Byteasar owns a logistics company. Its clients often have the company transport vast amounts of goods, which do not fit in a single truck. In such cases, Byteasar sends a convoy. Sometimes, there are more drivers than trucks in a convoy, with the spare drivers riding along as passengers. We assume that each truck can carry arbitrarily many passengers. The drivers can choose to stop the convoy at any moment. Before resuming the journey, the drivers can embark any of the trucks, and change behind the wheel. There are neither lower nor upper bounds on the number of stops along the way.

To increase road traffic safety, the Byteotian Ministry of Transport has mandated limits on the time a truck driver can spend behind the wheel. Each driver, having passed their periodic psychophysical tests, receives an entry in their driving license that tells how many kilometers they can spend behind the wheel on a single trip.

Byteasar has asked you to write a program that would help him manage his team of n truck drivers. The program must handle the following two types of events:

• Update of the entry in the i-th driver’s license. We assume that no driver has any entry in their driving license initially. Before receiving one, a driver cannot drive a truck.
• A query regarding the possibility of sending a convoy of c trucks on a route that is s kilometers long. As mentioned before, en route, the drivers can ride as passengers, and can freely swap. The shipments are handled sequentially, i.e., the next convoy sets out only once the previous one has returned.

The first line of the standard input contains two integers, n and m (1 ≤ n, m ≤ 1 000 000), separated by a single space, specifying the number of drivers and events respectively. The m lines that follow specify the events.

In case of an entry update, the line contains the letter U and two integers, k and a (1 ≤ k ≤ n, 0 ≤ a ≤ 1 000 000 000), indicating that the k-th driver can drive (behind the wheel) a kilometers in one trip from this point on. In case of a query, the line contains the letter Z and two integers, c and s (1 ≤ c ≤ n, 1 ≤ s ≤ 1 000 000 000), indicating a query about sending a convoy of c trucks on a route of s kilometers.

In tests worth 33% of the total score, the additional condition n, m ≤ 1000 holds. In tests worth 66% of the total score, the additional condition a, s ≤ 1 000 000 holds.

If the input contains z queries, then z lines should be printed to the standard output: the i-th one should contain the word TAK (Polish for YES) or NIE (Polish for NO), depending on the answer to the i-th input query.