Railways

Byteotia State Railways runs a single InterCity line through $c$ cities, numbered from $1$ to $c$ in the order the train visits them (city $1$ is the start and city $c$ is the end). The train has $s$ seats, and between any two consecutive stations it may carry at most $s$ passengers.

Seat reservation requests arrive one at a time and must be answered in the order they arrive. A single request asks for $n$ seats on the stretch from station $o$ to station $d$, so it occupies $n$ seats on every section between two consecutive stations from $o$ up to $d$, that is, sections $o, o+1, \dots, d-1$.

A request is accepted only when every one of those sections still has at least $n$ free seats at the moment it is processed. Partial fulfilment is not allowed: the train cannot serve only part of the route or fewer passengers than asked. When a request is accepted, the number of occupied seats on each affected section grows by $n$; when it is rejected, nothing changes.

Read the description of the line and the list of requests, decide which requests are accepted and which are rejected, and report the answer for every request.

The first line contains three integers $c$, $s$ and $r$ ($1 \le c \le 60000$, $1 \le s \le 60000$, $1 \le r \le 60000$), separated by single spaces: the number of cities on the line, the number of seats in the train, and the number of requests.

Each of the next $r$ lines describes one request in arrival order. Line $i+1$ holds the $i$-th request as three integers $o$, $d$ and $n$ ($1 \le o < d \le c$, $1 \le n \le s$), separated by single spaces: the origin station, the destination station, and the number of seats requested.

Print $r$ lines. On line $i$ print a single character: T if the $i$-th request is accepted, or N if it is rejected.