물류

Byteasar는 물류 회사를 운영한다. 고객들은 흔히 한 대의 트럭에 담을 수 없는 막대한 양의 화물을 운송해 달라고 요청한다. 이런 경우 Byteasar는 호송대를 보낸다. 호송대에는 트럭보다 운전자가 더 많을 때도 있으며, 남는 운전자는 승객으로 동승한다. 각 트럭은 승객을 임의로 많이 태울 수 있다고 가정한다. 운전자들은 언제든지 호송대를 멈출 수 있다. 여정을 재개하기 전에 운전자들은 아무 트럭에나 올라타서 운전대를 바꿀 수 있다. 도중에 정차하는 횟수에는 하한도 상한도 없다.

도로 교통 안전을 높이기 위해 Byteotia 교통부는 트럭 운전자가 운전대를 잡을 수 있는 시간에 제한을 두었다. 정기적인 심리신체 검사를 통과한 각 운전자는 운전면허에 한 번의 여정에서 운전대를 잡을 수 있는 거리가 몇 킬로미터인지 기재된 항목을 받는다.

Byteasar는 n명의 트럭 운전자로 구성된 팀을 관리할 프로그램을 작성해 달라고 요청했다. 프로그램은 다음 두 종류의 이벤트를 처리해야 한다.

• i번째 운전자의 면허 항목 갱신. 처음에는 어떤 운전자도 면허에 항목이 없다고 가정한다. 항목을 받기 전에는 운전자가 트럭을 운전할 수 없다.
• 길이 s킬로미터인 경로로 c대의 트럭으로 구성된 호송대를 보낼 수 있는지에 대한 질의. 앞서 말했듯이 도중에 운전자들은 승객으로 탑승할 수 있고 자유롭게 자리를 바꿀 수 있다. 화물은 순차적으로 처리된다. 즉, 다음 호송대는 이전 호송대가 돌아온 뒤에야 출발한다.

표준 입력의 첫 줄에는 두 정수 n과 m (1 ≤ n, m ≤ 1 000 000)이 공백 하나를 사이에 두고 주어진다. 이는 각각 운전자의 수와 이벤트의 수를 나타낸다. 이어지는 m개의 줄이 이벤트를 지정한다.

면허 항목 갱신의 경우 줄에 문자 U와 두 정수 k, a (1 ≤ k ≤ n, 0 ≤ a ≤ 1 000 000 000)가 주어진다. 이는 k번째 운전자가 이제부터 한 번의 여정에서 a킬로미터를 운전대를 잡고 운전할 수 있음을 나타낸다. 질의의 경우 줄에 문자 Z와 두 정수 c, s (1 ≤ c ≤ n, 1 ≤ s ≤ 1 000 000 000)가 주어진다. 이는 길이 s킬로미터인 경로로 c대의 트럭으로 구성된 호송대를 보내는 것에 대한 질의를 나타낸다.

전체 점수의 33%에 해당하는 테스트에서는 n, m ≤ 1000이라는 추가 조건이 성립한다. 전체 점수의 66%에 해당하는 테스트에서는 a, s ≤ 1 000 000이라는 추가 조건이 성립한다.

입력에 z개의 질의가 있으면 표준 출력에 z개의 줄을 출력한다. i번째 줄에는 i번째 입력 질의에 대한 답에 따라 TAK(폴란드어로 YES) 또는 NIE(폴란드어로 NO)를 출력한다.