题目背景

以此纪念某位七年级参加 NOIP，八年级挂在 CSP-S T2 的大佬。

题目描述

小 D 新入职了某国的交管部门，他的第一个任务是负责国家的一条长度为 $L$ 的南北主干道的车辆超速检测。为了考考小 D，小 W 制造了一辆速度为 $\infty$ 的汽车（这真的是汽车吗？），因此从点 $i$ 到点 $i+1$ 的时间可以为 $0$。

每一天早上，小 W 的车将会出现在主干道上，并从主干道上最南端 $1$ 号点的位置驶入向北行驶至最北端的 $n$ 号点。主干道上设置了 $m$ 组测速仪，其中第 $i$ 组测速仪测量主干道上任意一辆车从点 $l_i$ 到点 $r_i$ 所花费的时间。若这辆车的所花时间小于道路限制时间 $V_i$，那么这辆车就会被判定为超速。

然而，交通部门的政策总是朝令夕改。每天交通部门都会在凌晨增加或修改一条限制并在每天晚上将其删除或改回。为了睡懒觉， 小 W 每天都会计算从 $1$ 点到 $n$ 点所需的最短时间。 由于 $n$ 很大，小 W 想要使用编程解决这个问题，然而他不会，于是小 W 找到了你。

输入格式

第一行输入三个整数 $n, m, d$，分别表示点数，限制数和天数。

接下来 $m$ 行：

第 $i$ 行输入三个整数 $l_i, r_i, V_i$ 描述一条限制。

接下来 $d$ 行：

第 $i$ 行输入三个整数 $l_i, r_i, V_i$ 描述一条限制。如果初始限制中有 $l,r$ 与此相同的限制，则将旧的限制删除再增加新的限制，否则直接添加这条限制。

注意：每一次询问之间是互相独立的。

以上输入的 $l_i$ 和 $r_i$ 均满足 $l_i<r_i$。

输出格式

输出共 $d$ 行，每行一个整数，表示最短时间。

5 6 4
1 2 3
2 3 4
3 4 5
4 5 6
1 5 25
1 4 10
1 2 3
1 5 17
2 3 1
2 4 20

25
18
25
29

提示

对于 $20\%$ 的数据，$1\le n,m\le 100$，$1\le d\le 20$，$1\le V_i\le1000$。

对于 $50\%$ 的数据，$1\le n,m\le 1000$，$1\le d\le 1000$，$1\le V_i\le10^5$。

对于 $100\%$ 的数据，$1\le l_i<r_i\le n\leq 10^5$，$1\le V_i\le 10^9$ ，$1\le m,d\leq 10^5$。