E星球-农场主

题目描述

在 $3024$ 年，bessie 依然是 E 星球最大的农场主，一共有 $n$ 个牛群，牛群 $1\sim n$ 编号，每个牛群都有一定数量的奶牛。bessie 隔一段时间，会向第 $l$ 到第 $r$ 的牛群中的每个牛群增加 $c$ 头奶牛。在增加 $p$ 次后，bessie 进行 $q$ 次查询，每次查询，需要知道奶牛数量最接近 $x$ 并且不小于 $x$ 头的牛群与原来的编号是多少（如果有相同数字，输出最靠左的编号）？

输入格式

输入包含两个整数 $n,p$。 输入一行 $n$ 个数。 接下来 $p$ 行，每行三个整数 $l,r,c$，表示第 $l$ 到第 $r$ 的区间内，每个牛群增加 $c$ 头奶牛。 接下来输入一个 $q$。 接下来 $q$ 行，每行一个 $x$。

输出格式

最后输出bessie 隔一段时间，会向第 $l$ 到第 $r$ 的牛群中的每个牛群增加 $c$ 头奶牛。在增加 $p$ 次后，bessie有 $q$ 次查询，每次查询，需要知道奶牛数量最接近 $x$ 并且不小于 $x$ 头的牛群原来的编号是多少（如果有相同数字，输出最靠左的数据原来的编号，并且相同数据按照输入顺序排列）？

8 3
1 2 10 8 1 5 1 1
7 8 12
1 8 4
2 3 12
2
18
17

2
7

提示

#### 数据范围与提示 $5≤n,p≤100000，q≤1000000，1≤c≤10000，4<l,r,x

来源

童程童美