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

Сонымен қатар, \(M\) жұп үйлеспейтін батырлардың шектеулері бар. Әрбір \((u, v)\) жұбы үшін келесі шарт орындалады: егер бір команда \(u\) батырын таңдаса, екінші команда \(v\) батырын таңдай алмайды, және керісінше. Бұл үйлеспеушілік шектеулері қайшылық тудырмайды, яғни келесі шартты қанағаттандыратын батырлар тізбегін құру мүмкін емес: \(x_1, x_2, \ldots, x_k\) батырлары үшін әрбір \(1 \leq i \leq 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\) түрлі сан \(id_1, id_2, \dots, id_k\) (\(1 \le id_i \le N\)) келіп, олар таңдалған батырлардың индекстері болады. Кепілдік беріледі, яғни \(id_1, id_2, \dots, id_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