F. Хос талбай

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хос талбай нь олон нийтэд танигдсан азанд суурилсан тоглоом юм. 2 тоглогч хамтдаа тэгш өнцөгт үүсгэнэ. $n$ ширхэг бөмбөгтэй цүнх байгаа бөгөөд бөмбөг болгон дээр бүхэл тоонууд бичигдсэн байгаа. Эхний тоглогч цүнхнээс нэг бөмбөг харахгүй сугалах бөгөөд энэ бөмбөгөн дээр бичигдсэн тоо нь тэгш өнцөгтийн өргөний урт болох юм (энд бөмбөг болгон сугалагдах магадлал тэнцүү). Энэ бөмбөгийг буцааж цүнх уруу хийхгүй бөгөөд хоёр дахь тоглогч цүнхнээс дахин нэг өөр бөмбөг сугалж авна. Энэ бөмбөгөн дээрх тоо нь тэгш өнцөгтийн өндөр нь болно. Хэрвээ тэгш өнцөгтийн талбай $p$ тооноос их эсвэл тэнцүү бол тоглогчид ялна. Эсрэг тохиолдолд хожигдоно.

Тоглоомын шүүгчид $p$-д тохирох утгыг өгөх бөгөөд тэд $p$-г хосуудын хожих магадлал хэт их биш, хэт бага биш байхаар өгөх юм. Гэхдээ тэд тоолохдоо удаан, тиймээс танийг хэдэн асуултанд хариулуулахаар хөлсөлжээ. Танд бөмбөгөн дээрх тоонуудыг өгөх бөгөөд таниас $p$-ийн ялгаатай утгуудад тоглогчид ялах хэдэн ширхэг бөмбөгнүүдийн хослол байгааг мэдэхийг хүсжээ. Хэрвээ хос бөмбөгний эхний эсвэл хоёр дахь бөмбөг нөгөө хосын бөмбөгнүүдээс ялгаатай байх юм бол энэ 2 хосыг хоорондоо ялгаатай гэж үзнэ. Үүнээс гадна ижилхэн тоо бичигдсэн өөр бөмбөгнүүдийг ялгаатай гэж үзнэ.

Оролт

Эхний мөрөнд $n$ ($1 ≤ n ≤ 10^{6}$) бүхэл тоо өгөгдөнө.

2 дахь мөрөнд $n$ ширхэг эерэг бүхэл тоонууд $a_{i}$ ($1 ≤ a_{i} ≤ 3*10^{6}$) өгөгдөнө. Энд $i$ дэхь тоо нь $i$ дэхь бөмбөгөн дээр бичигдсэн тоо юм.

3 дахь мөрөнд $m$ ($1 ≤ m ≤ 10^{6}$) бүхэл тоо өгөгдөх бөгөөд энэ нь таниас асуух асуултын тоо юм.

4 дэхь мөрөнд $m$ ширхэг бүхэл тоонууд өгөгдөх бөгөөд $j$ дэхь тоо нь $j$ дэхь асуултын $p$ ($1 ≤ p ≤ 3*10^{6}$)-ийн утга болно.

Гаралт

Асуулт болгоны $p$-ийн утганд тоглогчид ялах хэдэн ширхэг хос бөмбөг байгааг хэвлэнэ үү. Хариулт болгоныг ялгаатай мөрөнд хэвлэнэ үү.

Орчуулсан: Энхлут

Жишээ тэстүүд

Оролт
5
4 2 6 1 3
4
1 3 5 8
Гаралт
20
18
14
10
Оролт
2
5 6
2
30 31
Гаралт
2
0
Сэтгэгдлүүдийг ачааллаж байна...