许多铁路长途客运的共同规则是每张车票都必须指定一个预留座位。这对于乘客来说相当方便，因为他们可以提前确保有空位。然而，这样的规则可能会导致“假性缺票”的问题。

考虑一个虽然少见但确实可能发生的情况。一列有两张座位的火车从 A 开往 C，中间只有 B 一个中途站。假设 1 号座位在 A-B 区段被购买，2 号座位在 B-C 区段被购买。因此，在 A 和 C 之间没有可以直接购买的空闲座位。然而，旅客可以购买 A-B 区段的 2 号座位和 B-C 区段的 1 号座位，并在旅途中从一个座位换到另一个座位。

你的任务是编写一个程序，在已知哪些车票已经售出的情况下，找出有多少对起点-终点站，满足：无法通过购买单张直达车票到达，但仍可以通过购买两张或更多张车票并在中途更换座位来到达。你可以认为，在特定的起点和终点之间，任何未售出的座位都可以被购买。

输入格式

第一行包含火车上的座位数 $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
10
6
2 9 10
3 5 9
1 2 10
2 1 4
2 7 8
3 1 2

输出样例 1

10

说明

这 10 对车站分别是：$(1, 3)$、$(1, 4)$、$(1, 5)$、$(1, 6)$、$(1, 7)$、$(2, 6)$、$(2, 7)$、$(3, 6)$、$(3, 7)$ 和 $(8, 10)$。

对于其他车站对，要么可以直接购买指定预留座位的直达车票，要么火车已经没有空余座位，即使乘客愿意购买分段车票并在旅途中更换座位也无法到达。