文件读写

• 输入文件water.in
• 输出文件water.out

限制

• 1000ms
• 512MB

题目描述

学校的花坛排成一排，共 $n$ 个，从左到右编号 $1 \sim n$。后勤程老师新配了一辆自动浇水车。这辆车的喷头很特别：在一次作业中，它的出水量会随着车子的前进而自动加大，越到后面的花坛浇得越多。程老师每天要开着它在花坛前来回跑好几趟，工作本上密密麻麻记满了作业记录。

工作本上一共记着 $q$ 次作业。一次作业记为四个整数 $l, r, a, d$，含义是：浇水车从第 $l$ 个花坛开始工作，一直到第 $r$ 个花坛收工（含两端）。第 $l$ 个花坛浇 $a$ 升水；之后车子每前进一个花坛，出水量都比前一个花坛多 $d$ 升——第 $l+1$ 个花坛浇 $a+d$ 升，第 $l+2$ 个花坛浇 $a+2d$ 升，……，第 $r$ 个花坛浇 $a+(r-l) \cdot d$ 升。当 $d=0$ 时，这次作业中出水量全程不变，覆盖到的每个花坛都浇 $a$ 升。

所有花坛的初始水量都是 $0$ 升。不同作业的浇水范围可以任意重叠，重叠部分的水量直接累加。$q$ 次作业全部完成后，每个花坛都有一个确定的总水量。

周末验收时，程老师不想把 $n$ 个花坛全部检查一遍，他打算抽查 $m$ 个花坛。抽查按他给出的顺序逐个进行：对每一次抽查，他给出一个花坛编号 $p$，你需要报告第 $p$ 个花坛此时的总水量是多少升。同一个花坛可能被重复抽查，每次都要照实回答。

输入格式

第一行三个整数 $n, q, m$，分别表示花坛个数、浇水作业次数和抽查次数。

接下来 $q$ 行，每行四个整数 $l, r, a, d$，表示一次浇水作业。

接下来 $m$ 行，每行一个整数 $p$，表示一次抽查的花坛编号。

输出格式

$m$ 行，第 $i$ 行一个整数，表示第 $i$ 次抽查的花坛的总水量（升）。

数据范围

特殊性质 A：所有作业的 $d$ 均为 $0$。

对于 $100\%$ 的数据，保证 $1 \leq n, q, m \leq 10^5$，$1 \leq l \leq r \leq n$，$1 \leq a \leq 10^3$，$0 \leq d \leq 10^3$，$1 \leq p \leq n$。部分测试点中单个花坛的总水量会超过 $2^{31} - 1$。

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

2
5
9
14
5

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

6
1
6
8

样例解释

样例1：第 $1$ 次作业中，花坛 $1 \sim 4$ 分别被浇 $2, 5, 8, 11$ 升；第 $2$ 次作业中，花坛 $3 \sim 5$ 分别被浇 $1, 3, 5$ 升。累加之后，花坛 $1 \sim 5$ 的总水量依次为 $2, 5, 9, 14, 5$ 升，$5$ 次抽查恰好询问全部五个花坛。