Екі команда ойынға кірісуге дайындалып жатыр. Әр команданың қолында $N$ батыр бар, олардың әрқайсысының күші $a_i$ деп берілген. Әр команда өзіне батырларды таңдайды, алайда бір батыр екі командада да таңдалмайды.

Сонымен қатар, $M$ жұп үйлеспейтін батырлардың шектеулері бар. Әрбір $(u,v)$ жұбы үшін келесі шарт орындалады: егер бір команда $u$ батырын таңдаса, екінші команда $v$ батырын таңдай алмайды, және керісінше. Бұл үйлеспеушілік шектеулері қайшылық тудырмайды, яғни келесі шартты қанағаттандыратын батырлар тізбегін құру мүмкін емес: $x_1,x_2,\dots ,x_k$ батырлары үшін әрбір $1\le i\le k$ шартында $x_i$ мен $x_{i+1}$ үйлеспейтін батырлар жұбы болып табылады (мұнда $x_{k+1}=x_1$ деп есептеледі) және $k>2$.

Ойын барысында $q$ сұраныс жүргізіледі. Әр сұраныста қарсылас команда кейбір батырларды таңдаған, және сізден сұралады: сіздің командаңыздың жалпы күші қарсылас команда күшінен артық болу үшін минималды қанша батырды қосу қажет екенін анықтаңыз. Егер мұндай команданы құру мүмкін болмаса, $-1$ шығарыңыз.

Енгізу

Бірінші қатарда екі бүтін сан $N$ және $M$ ($1\le N\le {10}^6$, $0\le M\le {10}^6$) берілген.

Екінші қатарда $N$ бүтін сан $a_1,a_2,\dots ,a_N$ ($1\le a_i\le {10}^9$) бар, мұнда әр сан батырдың күшін білдіреді.

Одан кейін $M$ қатар келіп, әр қатарда екі бүтін сан $u$ және $v$ ($1\le u,v\le N$, $u\ne v$) берілген — үйлеспейтін батырлар жұптары.

Келесі қатарда бір бүтін сан $q$ ($1\le q\le {10}^6$) көрсетілген — сұраныстар саны.

Әрбір келесі $q$ сұраныс былай беріледі: алдымен қарсылас команда таңдаған батырлар саны $k$ ($0\le k\le N$) беріледі, одан кейін $k$ түрлі сан $i{d}_1,i{d}_2,\dots ,i{d}_k$ ($1\le i{d}_i\le N$) келіп, олар таңдалған батырлардың индекстері болады. Кепілдік беріледі, яғни $i{d}_1,i{d}_2,\dots ,i{d}_k$ батырлар бір командада болуы мүмкін.

$K$ — барлық сұраныстардағы $k$ мәндерінің қосындысы. Кепілдік беріледі, $K\le {10}^6$.

Шығару

Әрбір сұраныс үшін бір бүтін сан шығарыңыз – сіздің командаңыздың жалпы күші қарсылас команда күшінен кем болмауы үшін қажет ең аз батыр саны, немесе егер мұндай команданы құру мүмкін болмаса, $-1$.

Бағалау жүйесі

Бұл есеп $9$ ішкі есептен тұрады. $K$ — барлық сұраныстардағы $k$ мәндерінің қосындысы.

Мысалдар

Енгізу 1

7 6
4 8 9 3 2 2 5
1 3
1 4
4 7
6 4
2 3
5 3
4
1 3
1 1
2 2 1
3 7 5 6

Жауап 1

3
1
-1
2

Енгізу 2

10 8
3 2 6 2 9 2 6 2 9 6
6 8
10 1
4 5
10 4
8 3
6 5
2 9
1 7
10
2 1 5
2 3 9
2 1 4
1 7
2 4 10
2 5 8
2 1 10
2 5 9
2 1 8
2 3 9

Жауап 2

2
3
1
1
1
2
2
4
1
3