{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e这一晚,TT 做了个美梦!\u003c/p\u003e\n\u003cp\u003e在梦中,TT 的愿望成真了,他成为了喵星的统领!喵星上有 $N$ 个商业城市,编号 $1$ ~ $N$,其中 $1$ 号城市是 TT 所在的城市,即首都。\u003c/p\u003e\n\u003cp\u003e喵星上共有 M 条有向道路供商业城市相互往来。但是随着喵星商业的日渐繁荣,有些道路变得非常拥挤。正在 TT 为之苦恼之时,他的魔法小猫咪提出了一个解决方案!TT 欣然接受并针对该方案颁布了一项新的政策。\u003c/p\u003e\n\u003cp\u003e具体政策如下:对每一个商业城市标记一个正整数,表示其繁荣程度,当每一只喵沿道路从一个商业城市走到另一个商业城市时,TT 都会收取它们($目的地繁荣程度 - 出发地繁荣程度$)$^ 3$(即两者相减的立方)的费用。\n\u003c/p\u003e\n\u003cp\u003eTT 打算测试一下这项政策是否合理,因此他想知道从首都出发,走到其他城市至少要交多少的税,如果总金额小于 $3$ 或者无法到达请悄咪咪地打出 \u0027?\u0027。 \u003c/p\u003e\n\n\n"}},{"title":"输入格式","value":{"format":"MD","content":"\u003cp\u003e第一行输入 $T$,表明共有 $T(1\\le T \\le 50)$ 组数据。\u003c/p\u003e\n\u003cp\u003e对于每一组数据,第一行输入 $N(1\\le N\\le200)$,表示点的个数。\u003c/p\u003e\n\u003cp\u003e第二行输入 $N$ 个整数,表示 $1$ ~ $N$ 点的权值 $a_i(0 \\le a_i \\le 20)$。\u003c/p\u003e\n\u003cp\u003e第三行输入 $M(0\\le M\\le 10^5)$,表示有向道路的条数。\u003c/p\u003e\n\u003cp\u003e接下来 $M$ 行,每行有两个整数$A, B$,表示存在一条 $A$ 到 $B$ 的有向道路。\u003c/p\u003e\n\u003cp\u003e接下来给出一个整数 $Q(0\\le Q \\le 10^5)$,表示询问个数。(0 \u003c\u003d Q \u003c\u003d 100000)\u003c/p\u003e\n\u003cp\u003e每一次询问给出一个 $P$,表示求 $1$ 号点到 $P$ 号点的最少税费。\u003c/p\u003e\n\n\n\n\n"}},{"title":"输出格式","value":{"format":"MD","content":"\u003cp\u003e每个询问输出一行,如果不可达或税费小于 $3$ 则输出 \u0027?\u0027。\u003c/p\u003e\n\u003cb\u003e注意:仅对于此题,输出时每行末尾的多余空格,不影响答案正确性。\u003c/b\u003e"}},{"title":"输入样例","value":{"format":"MD","content":"\u003cpre\u003e2\n\n5\n6 7 8 9 10\n6\n1 2\n2 3\n3 4\n1 5\n5 4\n4 5\n2\n4\n5\n\n2\n10 10\n1\n1 2\n1\n2\n\u003c/pre\u003e\n"}},{"title":"输出样例","value":{"format":"MD","content":"\u003cpre\u003eCase 1:\n3\n4\nCase 2:\n?\n\u003c/pre\u003e"}}]}