Бұл тапсырманың күрделі нұсқасы. Нұсқалар арасындағы айырмашылықтар $n$ және $q$ бойынша шектеулерде.

Айбар мен Батыр тастармен ойнағанды ұнатады. Оларда $n$ тас үйіндісі бар, ал $i$-ші үйіндіде $s_i$ тас бар. Олар кезекпен ойнайды, және бірінші кезек әрқашан Айбарда.

Әрбір жүрісте ойыншы кез келген бір үйіндіден белгілі бір мөлшерде тастарды алады. Айбар дәл $a$ тасты ала алады, ал Батыр дәл $b$ тасты ала алады. Егер ағымдағы ойыншы жүріс жасай алмаса (себебі қалған барлық үйінділерде тастар оның ала алатын мөлшерінен аз болса), онда ол жеңіледі.

Сіз $q$ сұранысқа жауап беруіңіз керек, мұнда әр сұраныс $a$ және $b$ сандарынан тұрады. Әр сұраныс үшін, егер екі ойыншы да оңтайлы ойнаса, берілген $a$ және $b$ мәндерімен ойынды кім жеңетінін анықтаңыз.

Енгізу

Бірінші жолда бір бүтін сан $n$($1\le n\le {10}^5$) — үйінділер саны.

Екінші жолда $n$ бүтін сан $s_1,s_2,\dots ,s_n$($1\le s_i\le {10}^9$) — әр үйіндідегі тастар саны.

Үшінші жолда бір бүтін сан $q$($1\le q\le {10}^6$) — сұраныстар саны.

Келесі $q$ жолдың әрқайсысында екі бүтін сан $a,b$($1\le a,b\le 1000$) болады.

Шығару

Әр $q$ ойын үшін жеңімпаздың бірінші әрпін шығарыңыз.

Мысалдар

Енгізу 1

4
4 6 9 3
2
2 3
1 1

Жауап 1

AB