Railway Tickets

Long distance trains sell one reserved seat per ticket. A passenger knows in advance that a seat is waiting, but the rule makes free seats look sold out.

Consider a train with two seats that runs from station A to station C and stops once at station B. Seat 1 is sold for A to B, and seat 2 is sold for B to C. No single seat is free for the whole trip from A to C. A traveler can still buy seat 2 for A to B and seat 1 for B to C, then change seats at station B.

Call the stretch of the route between two neighbouring stations a leg. Given the tickets that are already sold, count the pairs of a departure station and an arrival station that can be travelled only by buying two or more tickets and changing seats on the way. Any seat that is not sold on a leg can be bought.

The exact condition is this. For two stations $s < f$, the trip from $s$ to $f$ is possible when every leg between them has at least one free seat. The pair $(s, f)$ is counted when the trip is possible and no single seat is free on all of the legs from $s$ to $f$ at once.

The first line contains the number of seats in the train $K$ ($3 \le K \le 1000$). The second line contains the number of stations on the route $N$ ($3 \le N \le 10000$). The third line contains the number of tickets already sold $T$ ($0 \le T \le \min(10^5,\ K(N-1))$).

Each of the next $T$ lines contains three integers $pl$, $st$, $fn$ describing one ticket. $pl$ is the number of the reserved seat; seats are numbered from $1$ to $K$ over the whole train, without splitting by carriage. $st$ and $fn$ are the departure and the arrival station; stations are numbered from $1$ to $N$ along the route. Every ticket has $st < fn$. One seat can carry several tickets, but their ranges do not overlap: the next ticket for a seat starts at the station where the previous one ends, or later on the route.

Print one integer, the number of station pairs.

The ten pairs in the example are $(1, 3)$, $(1, 4)$, $(1, 5)$, $(1, 6)$, $(1, 7)$, $(2, 6)$, $(2, 7)$, $(3, 6)$, $(3, 7)$ and $(8, 10)$. For every other pair, either one direct ticket with a reserved seat is available, or some leg has no free seat, so the trip is impossible even for a passenger who buys several tickets and changes seats.