Migrated from Lutece 2934 回村の诱惑

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag: 线段树 时隔多年，特工李三光为了营救总统被绑架的女儿碍事梨再次踏上了回村之路。这次村民们依旧热情地“招待”了三光，并且在他进村的路上设置了很多陷阱。

假设三光进村的路是连续的 $n$ 块地，其中共有 $m$ 个陷阱，第 $i$ 个陷阱的布置区间为 $[l_i, r_i]$，表示在第 $l_i$ 块和第 $r_i$ 块地之间（包含边界）布置有陷阱，在 $t1_i$ 时刻完成布置，陷阱的持续时间为 $t2_i$ (在 $t1_i + t2_i$ 时刻，该陷阱视为已不存在）。在情报员哈尼根的帮助下，他获取了村民们布置陷阱的所有情报，并且考虑了 $q$ 种进村情况。

具体来说，三光在考虑第 $i$ 种情况时，假定时刻为 $t3_i$ ，并且只在乎区间 $[ql_i, qr_i]$ 内一共有多少块地没有被布置陷阱。为了让三光成功营救碍事梨，请你帮忙计算这个值。

Input

第一行输入三个整数 $n$, $m$ 和 $q$，表示进村的路段长为 $n$，共有 $m$ 个陷阱，三光考虑了 $q$ 种进村情况。

接下来的 $m$ 行每行输入四个数，第 $i$ 行输入的四个数 $l_i$，$r_i$ ，$t1_i$ 和 $t2_i$，分别表示陷阱的布置区间、完成布置的时刻以及陷阱的持续时间。

最后 $q$ 行每行输入三个数字，第 $i$ 行输入的三个数 $ql_i$, $qr_i$ 和 $t3_i$，分别表示三光考虑第 $i$ 种进村情况时在乎的区间以及时刻。

Output

输出共 $q$ 行，每行输出一个整数，表示第 $i$ 种情况下没有被布置陷阱的路段长度总和。

Samples

5 3 3
2 4 1 3
1 3 2 5
3 5 3 5
1 5 2
2 3 4
3 5 8

1
0
3

Constraints

$1 \leq n, m, q \leq 2 \times 10^5$，$1 \leq l_i \leq r_i \leq n$，$1 \leq ql_i \leq qr_i \leq n$，$1 \leq t1, t2, t3 \leq 2 \times 10^5$

输入数据均为整数。

Resources

2023 UESTC ICPC Training for Data Structures