concurs

Time limit: 0.3s Memory limit: 128MB Input: concurs.in Output: concurs.out

Andor este o planetă foarte foarte îndepărtată de planeta noastră. Totuși, oamenii și andorenii (locuitorii planetei Andor) au foarte multe lucruri în comun. Unul dintre aceste lucruri este pasiunea pentru șah.

Andorenii nu se descurcă foarte bine cu organizarea evenimentelor, așadar te roagă pe tine să îi ajuți să organizezi un concurs de șah pentru copii mici. Însă, andorenii nu au stabilit o limită maximă de vârstă pentru a considera un jucător să fie copil. Tu ai posibilitatea să o alegi.

Se știe că sunt NN participanți la acest concurs, pentru fiecare cunoști următoarele două lucruri:

  • Cât de bun este jucătorul la șah (11 e cel mai slab scor, 10910^9 e cel mai bun scor);
  • Vârsta pe care o are.

Tu ai favoriți la acest concurs, așadar ai vrea să răspunzi la QQ întrebări de forma: Dacă limita de vârsta ar fi de tt ani, cine ar câștiga concursul?

Cerință

Se dă NN și două șiruri s1,s2,sNs_1, s_2, \dots s_N și v1,v2,vNv_1, v_2, \dots v_N. De asemena, se dă QQ și cele QQ interogări. Află răspunsul pentru fiecare întrebare.

Date de intrare

Pe prima linie a fișierului de intrare concurs.in se află numărul NN. Pe a doua linie se află șirul s1,s2,sNs_1, s_2, \dots s_N. Pe a treia linie se află șirul v1,v2,vNv_1, v_2, \dots v_N. Pe a treia linie se află numărul QQ și pe următoarele QQ linii se află câte un număr tt pe fiecare linie.

Date de ieșire

Să se afișeze în fișierul concurs.out QQ linii. A ii-a linie fiind răspunsul pentru a ii-a întrebare.

Restricții și precizări

  • 2N,Q200 0002 \leq N, Q \leq 200 \ 000
  • 1si,vi,t1091 \leq s_i, v_i, t \leq 10^9
  • Unitatea de timp folosită pe planeta Andor este diferită față de unitatea de timp folosită pe Terra, așadar participanții pot avea foarte foarte mulți ani.
  • Se garantează că valorile șirului ss sunt distincte!
  • Se garantează că pentru fiecare întrebare, există cel puțin un participant care poate participa la concurs
# Punctaj Restricții
1 25 N,Q2 000N, Q \leq 2 \ 000
2 20 t,vi3t, v_i \leq 3
3 30 t,vi106t, v_i \leq 10^6
4 25 Fără restricții suplimentare

Exemplu

concurs.in

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

concurs.out

4
4
4
6
5
5
5
1
1
1
1
1

Explicație

Dacă limita de vârstă ar fi de 44 ani, atunci particpanții ar fi cei cu numerele 22, 44, 66. Scorurile lor fiind 22, 33, 44. Deci, câștigătorul ar fi al 66-lea participant.

Dacă limita de vârstă ar fi de 1010 ani, ar concura toți cei NN participanți. Așadar, câștigătorul ar fi primul participant (are scorul 1010).

Log in or sign up to be able to send submissions!