题目背景

• 曼哈顿计划EX， The X Makes It Sound Cool

• 艾登黑进了dedsec的系统以后，发现核弹发射已经进入了倒计时，他必须停止核弹的发射进程。

题目描述

• 艾登拥有一个计算机网络，每一台计算机都至少有着Intel Xeon E50 v40 + 40路GTX10800Titan的恐怖配置，并由无线网络直接或间接连接，这可以用一个无向连通图来表示。但是他的计算机网络有一个问题——不够安全，dedsec可能会攻击他的网络，切断一些无线连接，从而导致整个计算机网络不连通。为了避免这种情况，艾登决定从这些计算机中挑出一些计算机作为计算节点，其他计算机作为信息的中转站，进行停止核弹发射进程的任务。虽然台台都是顶配，但是艾登的计算机也会有从山寨厂买回的配件和原装正版配件的差别——每台电脑的工作能力是不同的，记为$w_{i}$。现在艾登想知道，对于一个工作能力的要求，整个网络的安全系数最大是多少？

• 设给出的图为$G = (V , E)$，其中$V$ = $V_{1}$（计算节点） + $V_{2}$（中转节点）

• 我们定义安全系数k为：最大的k，使得任意两点$u,v\in V_{1}$都至少有k条互不相交的u到v的链（互不相交定义为：没有重复的边，可以重复有重复的点）

• 我们定义整个图的工作能力$W = \sum_{v \in V_{1}}{w_{v}}$

输入格式

• 第1行，三个整数n,m,q表示有n台计算机，m个无线网络，q次询问

• 第2行，n个整数，表示计算机的$w_{i}$

• 第3行到m+2行，每行两个整数u,v，表示有u，v之间存在直接的无线网络，什么都不保证

• 第m+3行到m+q+2行，每行一个整数k，表示一个询问

输出格式

• 一共q行，每行一个整数，表示要达到k的工作能力的前提下，整个网络最大的安全系数，如果只用一台计算机就能满足要求，输出"nan"

• 如果没有办法满足需求，输出"Nuclear launch detected"

• 仅输出nan并不能得分

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

nan
2
Nuclear launch detected

提示

样例解释

• 对于询问1，选择任何一台计算机作为计算节点都是一个合法答案

• 对于询问2，至少要选择3台计算机，任选三个都是合法方案。选出的三个点构成三角形，对于任意两个点都有两种相互到达的方法（在三角形上顺时针和逆时针走），所以答案是2

• 对于询问3，选择所有的计算机都不足以满足任务

数据规模

• 对于30%的数据，n<=20，保证 $qn^{4}$ 不大于1e8

• 对于100%的数据，n<=550,m<=3000,q<=2017,询问以及$w_{i}$均不超过$10^{6}$

• 所有数字均为正整数