intalnire

Time limit: 0.3s
Memory limit: 256MB
Input:
Output:

În orașul programatorilor există un local celebru unde lumea se poate distra cât dorește, la orice oră. Primarul orașului programatorilor a construit, pornind de la acest local, mai multe străzi către casele tuturor cetățenilor, case codificate cu numere de la 22 la nn, localul fiind codificat cu 11. Dacă între o casă și local nu există alte case, atunci drumul este construit direct între cele două imobile, dar dacă între casă și local există și alte case, atunci drumul va fi format din drumul de la local la prima casă, apoi se va construi drumul de la prima casă la a doua casă, apoi de la a doua casă la a treia casă și tot așa până se ajunge la casa curentă.

Orașul este codificat sub forma unui vector t[ ]t[\ ], unde t[i]=0t[i] = 0 dacă imobilul ii este exact localul unde se pot distra oamenii din oraș sau t[i]=yt[i] = y, cu y0y \neq 0, cu semnificația că de la casa ii se poate ajunge la casa/imobilul yy care se află între local și casa curentă.

Andrei și Alexandru sunt locuitori ai acestui oraș. Ei stau la casele cu codul x1x_1, respectiv x2x_2. Ei doresc să se întâlnească în drum spre local unde se vor distra, prin urmare doresc să alfe care este prima casă la care pot amândoi să ajungă, în drum spre local.

Cerința

Pentru qq întrebări de forma "care este prima casă unde Andrei și Alexandru se pot întâlni, dacă aceștia locuiesc la casele x1x_1 și x2x_2?", să se alfe răspunsul la aceste întrebări.

Date de intrare

Pe prima linie se vor găsi numerele nn și qq. Pe a doua linie se va găsi vectorul t[ ]t[\ ], cu semnificația din enunț, pentru toți indicii de la 22 la nn. Pentru i=1i = 1, se consideră t[i]=0t[i] = 0.
Pe următoarele qq linii se vor găsi câte două numere x1x_1 și x2x_2, cu semnificația din enunț.

Date de ieșire

Se va afișa răspunsul pentru fiecare întrebare, pe linii diferite.

Restricții și precizări

  • 1n100 0001 \leq n \leq 100 \ 000;
  • 1q4 000 0001 \leq q \leq 4 \ 000 \ 000;
  • Există exact un drum de la local la fiecare casă din orașul programatorilor.
  • Este recomandat să folosiți citirea rapidă cu aceste linii de cod la începutul funcției main(): cin.tie(0)->sync_with_stdio(0);.

Exemplu

stdin

5 2
1 1 2 2
1 2
4 5

stdout

1
2

Problem info

ID: 282

Editors:

Author:

Source: Concursul SOLINFO.ro Runda 1

Tags:

Concursul SOLINFO.ro Runda 1

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