#ZF1174. 小黄食堂鸡腿配送大大大挑战

小黄食堂鸡腿配送大大大挑战

Description

在一个宁静而美丽的校园里,住着一位名叫小黄的学生。校园生活丰富多彩,但最让小黄和他的小伙伴们期待的是一天中的食堂时光。食堂以提供美味的鸡腿闻名,每天都有很多学生排队等待那一份特别的午餐。

然而,这个食堂有着一个独特的配送机制。沿着校园内一条虚拟的坐标轴分布着 nn 个食堂窗口,每个窗口都有自己的服务范围,左右边界分别为 lil_irir_i ,和特定数量的鸡腿 xix_i 可供分发。小黄发现,尽管每个窗口都尽力满足学生的需求,但由于资源有限,只有站在特定位置的学生才能获得足够的鸡腿。

小黄有 qq 个好朋友,一天,小黄的好朋友们向他表达了各自对鸡腿的喜爱,并希望能吃到不同数量 yiy_i 的鸡腿。为了帮助他的朋友们实现愿望,小黄决定利用他对校园布局的了解,找出每个朋友应该站在坐标轴上的哪个位置,以便他们能够得到心仪的鸡腿数量。这不仅是一场关于寻找美食的冒险,也是智慧与友谊的考验。

小黄知道,如果他能解决这个问题,那么他和他的小伙伴们就能在午餐时间享用到他们最爱的鸡腿了。请你告诉小黄每个朋友需要站哪个位置才能吃到对应数量的鸡腿。

注:如果站在一个位置,能够送到那个位置的食堂都会把所有 xix_i 个鸡腿送过来,如果收到的鸡腿数量不等于那个同学期望吃到的鸡腿数量就无法满足他的要求。

Format

Input

第一行给出两个整数 n,qn,q, 其中 1n,q1051\leq n,q \leq 10^5,分别表示有多少个食堂窗口,小黄有多少个好朋友。

接下来 nn 行,每行给出两个整数 li,ri,xil_i,r_i,x_i,其中 0liri109,1xi1050\leq l_i \leq r_i \leq 10^9 ,1\leq x_i \leq 10^5,表示第 ii 个窗口的服务范围。

最后一行给出 qq 个整数 a1,a2,,aqa_1, a_2, \ldots, a_q,其中 1aii=1nxi1\leq a_i \leq \sum_{i=1}^{n} x_i,分别表示每个好朋友想吃的鸡腿数量。

Output

一共输出 qq 行,每行输出一个整数 xx,其中 0x1090 \leq x \leq 10^9,表示满足这个朋友所需要的鸡腿个数所站的位置,如果找不到对应的位置,输出 1-1 。(满足多个答案输出任意一个即可)

Samples

3 4
1 3 3
2 3 3
3 3 3
9 6 3 2
3
2
1
-1

Limitation

2s, 256KiB for each test case.