曾经在一个森林中居住着 N 只好斗的猴子。在最初他们我行我素，互不认识。但是猴子们不能避免争吵，且两只猴子只会在不认识对方时发生争吵，当争吵发生时，双方会邀请它们各自最强壮的朋友并发起决斗（决斗的为各自最强壮的朋友）。当然，在决斗之后两只猴子和他们各自的伙伴都认识对方了（成为朋友），虽然他们曾经有过冲突，但是他们之间绝不会再发生争吵了。
假设每只猴子有一个强壮值，强壮值将在一场决斗后减少为原先的一半（例如 10 会减少到 5，而 5 会减少到 2，即向下取整）。
我们也假设每只猴子都认识它自己（是自己的朋友）。即当他是他朋友中最强壮的，他自己就会去决斗。
有多组数据，每一组数据有两部分。
第一部分：第一行包含一个整数 N 表示猴子的数量。后为 N 行，每行一个数字为第 i 只猴子的强壮值 s_{i}。
第二部分：第一行包含一个整数 M 表示发生了 M 次冲突。后为 M 行，每行两个整数 x 和 y，表示第 x 只猴子和第 y 只猴子之间发生了冲突。
对于每次冲突，如果两只猴子认识对方，输出 -1，否则输出决斗后他们朋友中最强壮的猴子的强壮值。
5 20 16 10 10 4 5 2 3 3 4 3 5 4 5 1 5
8 5 5 -1 10
N,M\leq 100000，s_i \leq 32768
luogu