자리를 옮기는 기차표

장거리 열차는 표 한 장마다 좌석을 하나씩 지정해서 판다. 승객은 앉을 자리가 있다는 것을 미리 알 수 있지만, 이 방식은 남은 자리를 없는 것처럼 보이게 만든다.

좌석이 두 개인 열차가 A역을 떠나 B역에 한 번 서고 C역까지 간다고 하자. 1번 좌석은 A에서 B까지 팔렸고, 2번 좌석은 B에서 C까지 팔렸다. A에서 C까지 한 좌석으로 가는 표는 남아 있지 않다. 그래도 A에서 B까지는 2번 좌석을, B에서 C까지는 1번 좌석을 사고 B역에서 자리를 옮기면 A에서 C까지 갈 수 있다.

이웃한 두 역 사이를 구간이라고 하자. 이미 팔린 표가 주어질 때, 표를 두 장 이상 사고 도중에 자리를 옮겨야만 갈 수 있는 (출발역, 도착역) 쌍의 개수를 구하는 프로그램을 작성하시오. 어떤 구간에서 팔리지 않은 좌석은 언제든 살 수 있다고 가정한다.

정확한 조건은 이렇다. 두 역 $s < f$에 대해, $s$와 $f$ 사이의 모든 구간에 비어 있는 좌석이 하나 이상 있으면 자리를 옮겨 가며 $s$에서 $f$까지 갈 수 있다. 이 조건을 만족하면서 $s$부터 $f$까지 전 구간이 통째로 비어 있는 좌석이 하나도 없을 때, 쌍 $(s, f)$를 센다.

첫째 줄에 열차의 좌석 수 $K$ ($3 \le K \le 1000$)가 주어진다. 둘째 줄에 노선의 역 수 $N$ ($3 \le N \le 10000$)이 주어진다. 셋째 줄에 이미 팔린 표의 수 $T$ ($0 \le T \le \min(10^5,\ K(N-1))$)가 주어진다.

다음 $T$개 줄에는 표 한 장을 나타내는 세 정수 $pl$, $st$, $fn$이 주어진다. $pl$은 예약된 좌석 번호이고, 좌석은 객차를 구분하지 않고 열차 전체에 걸쳐 $1$부터 $K$까지 번호가 붙어 있다. $st$와 $fn$은 각각 출발역과 도착역이며, 역은 노선을 따라 $1$부터 $N$까지 번호가 붙어 있다. 모든 표에서 $st < fn$이다. 한 좌석에 표가 여러 장 팔릴 수 있지만, 그 표들의 구간은 서로 겹치지 않는다. 같은 좌석의 다음 표는 앞 표가 끝나는 역에서 출발하거나 그보다 뒤에서 출발한다.

조건을 만족하는 역 쌍의 개수를 한 줄에 출력한다.

예제에서 세는 쌍은 $(1, 3)$, $(1, 4)$, $(1, 5)$, $(1, 6)$, $(1, 7)$, $(2, 6)$, $(2, 7)$, $(3, 6)$, $(3, 7)$, $(8, 10)$의 10개다. 나머지 쌍은 좌석이 지정된 표 한 장으로 갈 수 있거나, 아니면 어느 구간에 빈 좌석이 없어서 표를 여러 장 사고 자리를 옮겨도 갈 수 없다.