Problem Description

A train departs from city $1$ and travels to city $C$. The train has $S$ seats, and there are $R$ ticket booking requests.

Each booking request consists of three integers $O, D, N$, meaning that $N$ seats are requested for the trip from station $O$ to station $D$.

If there are enough available seats throughout the requested segment, then the request can be satisfied; otherwise, it cannot.

Process the requests in the given order, and determine whether each request can be satisfied.

Input Format

The first line contains three integers $C, S, R$.

The next $R$ lines each contain three integers $O, D, N$, describing one booking.

Output Format

For the $i$-th booking, if it can be satisfied, output T, otherwise output N.

4 6 4
1 4 2
1 3 2
2 4 3
1 2 3

T
T
N
N

Hint

Constraints: $1 \le C, S, R \le 60000$.

Translated by ChatGPT 5