问题描述

甜甜圈师傅的早晨很早。D先生，也称为甜甜圈先生，是一个了不起的甜甜圈师傅。今天也是如此，他走进自己的厨房，在日出前准备做甜甜圈。

眨眼间，D先生就用纯熟的手法炸制出了$N$只甜甜圈。但是这些甜甜圈不能直接展示在橱窗里。需要进行奶油填充、沾上巧克力、装饰可爱的彩色物品等多个装饰任务。这里有$K$个任务，编号从1到K，每个任务必须按照顺序$1,2，\ldots,K$完成，才能将甜甜圈作为销售商品。

D先生立刻将这$N$只甜甜圈排成一排。他似乎打算一次性顺序完成每个装饰任务。然而，他到底在做什么？D先生昨晚熬夜了，只装饰了一部分连续区间的甜甜圈。这显然是一个错误！不仅如此，他还会跳过一些任务，有时可能不执行任何任务，任务的顺序也可能错乱。没有按照正确流程装饰的甜甜圈不能作为销售商品，所以他应该将它们丢弃。

幸运的是，有一些记录了他所做任务序列的数据。数据包含以下信息：对于每个任务，装饰甜甜圈连续区间$[l, r]$和任务编号$x$。请编写一个程序，在给定的记录数据中枚举可以展示在橱窗中作为销售商品的甜甜圈的数量。

输入

输入包含一个单独的测试用例。测试用例的格式如下所示。

$N$ $K$
$T$
$l\_1$ $r\_1$ $x\_1$
:
:
$l\_T$ $r\_T$ $x\_T$

第一行包含两个整数$N$和$K$，其中$N$（$1 \leq N \leq 200{,}000$）是D先生炸制的甜甜圈的数量，$K$（$1 \leq K \leq 200{,}000$）是应该应用于甜甜圈上的装饰任务的数量。第二行包含一个整数$T$（$1 \leq T \leq 200{,}000$），表示D先生完成的任务的信息数量。接下来的$T$行中，每行包含三个整数$l\_i$，$r\_i$和$x\_i$，表示D先生完成的第$i$个任务：第$i$个任务应用于甜甜圈的区间$[l\_i, r\_i]$（$1 \leq l\_i \leq r\_i \leq N$），任务编号为$x\_i$（$1 \leq x\_i \leq K$）。

输出

输出可以作为销售商品的甜甜圈的数量。

示例输入1

3 2
3
1 2 1
2 3 2
3 3 1

示例输出1

1

示例输入2

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

示例输出2

2

示例输入3

10 1
2
2 9 1
5 7 1

示例输出3

5