该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间工程师

题目描述

徐老师来考考你，给定一张包含 $n$ 个点的无向图，点从 $1$ 到 $n$ 编号。图中初始没有任何边，任意两点均不连通。

每个点 $i$ 有一个非负权值 $w_i$。一个连通块的权值定义为该连通块内所有点权值之和。

接下来会发生 $m$ 次架桥操作，每次操作会在某个时间点把两点之间连上一座桥（加入一条无向边）。随后有 $Q$ 次查询，每次查询会问：在某个时间点 $T$，最大连通块的权值是多少。

时间点采用“时间戳”定义：

每次架桥操作给出时间戳 $t$，表示该边在时间 $t$ 生效

一次查询给出时间 $T$，表示只考虑所有满足 $t ≤ T$ 的架桥操作已经生效后的图

若同一时间戳下有多次架桥，它们在该时间点同时生效

重复架桥（同一对点多次添加边）不会产生额外影响

你需要按顺序回答所有查询。

输入格式

第一行输入三个整数 $n\ m\ Q（1 ≤ n, m, Q ≤ 2×10^5）$，分别表示点数、架桥操作数与查询数。
第二行输入 $n$ 个整数 $w_1, w_2, ..., w_n$，表示每个点的权值$（0 ≤ w_i ≤ 10^9）$。

接下来 $m$ 行，每行三个整数 $t \ u \ v$，表示在时间戳 $t$ 架桥连接 $u 与 v$：$(1 ≤ u, v ≤ n),(0 ≤ t ≤ 10^9)$

接下来 $Q$ 行，每行一个整数 $T$，表示查询时间点$（0 ≤ T ≤ 10^9）$。

输出格式

对于每个查询，输出一行一个整数，表示在时间 $T$ 时（即所有 $t ≤ T$ 的桥梁均加入后）图中最大连通块的权值。

输入输出样例 #1

输入 #1

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

输出 #1

5
7
15

说明/提示

样例解释

• 时间 0：无边，最大连通块为单点 {5}，权值 5

• 时间 3：生效边 (1,2) 与 (3,4)，连通块权值分别为 3、7、5，最大为 7

• 时间 5：所有边生效，最终最大连通块权值为 15