DRŽAVNO NATJECANJE 2015. – Drugi dan natjecanja / Srednja škola, II. podskupina (3. i 4. razred) - 3. zadatak

Mirko i Slavko igraju igru na ploči koja, začudo, ovaj put nije nužno pravokutnog oblika, ali se ipak sastoji od skupa međusobno povezanih jediničnih kvadratića.

Točnije, njihova ploča za igru se sastoji od traka u obliku stupaca poredanih jedan do drugog s lijeva na desno. Svaka traka se sastoji od jednog ili više jediničnih kvadratića, a složene su tako da se dvije susjedne trake uvijek dodiruju barem duž jednog cijelog kvadratića

U jednoj partiji igre, zadaju se početni i završni kvadratić te se traži udaljenost između ta dva kvadratića.

Pritom, udaljenost definiramo kao broj koraka potreban da se dođe od jednog kvadratića do drugog ako je u svakom koraku dozvoljen skok na susjedni kvadratić (gore, dolje, lijevo ili desno) koji se nalazi unutar ploče za igru.

Napišite program koji će za zadanu ploču, te za svaki zadani par početnih i završnih kvadratića odrediti njihovu udaljenost.

Kako bi mogli označiti pojedina polja, smatramo da se ploča za igru nalazi unutar kvadratne ploče koje se sastoji od redaka označenima brojevima 1, 2, … odozgo prema dolje i stupaca označenih brojevima 1, 2, … s lijeva na desno.

Trake su označene brojevima od 1 do N. Traka K se nalazi u K-tom stupcu ploče te je opisana sa dva broja Ak i Bk - redak najgornjeg i najdonjeg kvadratića trake.

Ulazni​ podaci

U prvom redu nalaze se dva prirodna broja, N i Q (1 ≤ N, Q ≤ 200000)- broj traka te broj parova početnih i završnih polja. U K-tom od sljedećih N redova nalaze se dva prirodna broja Ak i Bk (1 ≤ Ak ≤ Bk ≤ 10^9) - najgornji odnosno najdonji redak kvadratića K-te trake.

Za svake dvije susjedne trake postojat će barem jedan redak takav da obje sadrže kvadratić u tom retku.

U svakom od sljedećih Q redova nalaze se po četiri prirodna broja Rp, Sp, Rz, Sz (1 ≤ Rp, Rz ≤ 10^9, 1 ≤ Sp, Sz ≤ N) - redak i stupac početnog te završnog kvadratića. Oba kvadratića će se nalaziti unutar ploče za igru.

Izlazni podaci

Potrebno je ispisati Q redova. U K-ti red ispišite udaljenost između K-tog po redu para kvadratića sa ulaza.

Napomena: Preporučamo da koristite 64-bitni cjelobrojni tip podataka (int64 u Pascalu, long long u C/C++)

Primjeri test​ podataka

Ulaz

4 3
2 3
1 4
3 4
2 3
2 1 3 2
3 1 3 4
2 1 2 4

Izlaz

2
3
5

Ulaz

6 4
3 6
2 5
2 3
1 5
4 4
2 6
2 6 1 4
6 6 4 1
3 4 3 1
6 1 6 1

Izlaz

7
9
3
0