철도 좌석 예약

바이테아 국영 철도는 도시 $c$개를 지나는 인터시티 노선 하나를 운행한다. 도시는 열차가 지나는 순서대로 $1$번부터 $c$번까지 번호가 매겨져 있으며, $1$번 도시가 출발지이고 $c$번 도시가 종착지이다. 열차의 좌석 수는 $s$개이고, 서로 이웃한 두 역 사이의 구간에서는 최대 $s$명까지만 태울 수 있다.

좌석 예약 요청은 한 번에 하나씩 들어오며, 들어온 순서대로 처리해야 한다. 하나의 요청은 $o$번 역에서 $d$번 역까지 가는 구간에 좌석 $n$개를 예약해 달라는 것으로, 이웃한 두 역 사이의 모든 구간 $o, o+1, \dots, d-1$에서 좌석을 $n$개씩 차지한다.

요청은 그것이 차지하는 모든 구간에 남은 좌석이 $n$개 이상일 때에만 받아들여진다. 일부만 처리하는 것은 허용되지 않으며, 경로의 일부만 태우거나 요청한 인원보다 적게 태울 수 없다. 요청이 받아들여지면 해당 구간들의 사용 중인 좌석 수가 각각 $n$만큼 늘어나고, 거절되면 아무것도 바뀌지 않는다.

노선 정보와 요청 목록을 읽어 각 요청이 받아들여지는지 거절되는지 판정하고, 모든 요청에 대한 답을 출력하라.

첫째 줄에 세 정수 $c$, $s$, $r$ ($1 \le c \le 60000$, $1 \le s \le 60000$, $1 \le r \le 60000$)이 공백 하나로 구분되어 주어진다. 각각 노선의 도시 수, 열차의 좌석 수, 요청의 수를 뜻한다.

다음 $r$개의 줄에는 요청이 들어온 순서대로 하나씩 주어진다. $i+1$번째 줄에는 $i$번째 요청이 세 정수 $o$, $d$, $n$ ($1 \le o < d \le c$, $1 \le n \le s$)으로 공백 하나로 구분되어 주어진다. 각각 출발역 번호, 도착역 번호, 요청한 좌석 수를 뜻한다.

$r$개의 줄을 출력한다. $i$번째 줄에는 문자 하나를 출력하는데, $i$번째 요청이 받아들여지면 T를, 거절되면 N을 출력한다.