Бұл тапсырманың күрделі нұсқасы. Нұсқалар арасындағы айырмашылықтар \(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,\ldots, 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