Vladuţ are o bucată de pamânt, în formă de triunghi echilateral de latură 2 N, avand fiecare celulă de lungime 1 numerotată ca în Fig 1 (N = 2). El trebuie să plătească impozit pentru fiecare celulă de lungime unu, în funcţie de zonele de care aceasta aparţine. O astfel de celulă poate să aparţină mai multor zone, pe care le determinăm în modul următor: se duc liniile mijlocii ale triunghiului curent, obţinându-se astfel 4 triunghiuri de lungime L/2, care pot fi fie din tipul celui din Fig 2, fie din Fig 3. Se adună la impozitul total impozitul pentru zona curentă (care se deduce din Fig 2 sau Fig 3). Se reia procedeul având ca nou triunghi zona în care celula se află, până se ajunge la un triunghi de lungime 1.
De exemplu, pornim cu un triunghi de latură 4 (N = 2) şi dorim să calculăm impozitul pentru celula (3, 2). La prima descompunere, observăm că celula (3, 2) se află în triunghiul format din (3,2), (3,3), (3, 4), (4, 4). Conform Fig 2, costul pentru această zonă este 2. Noul triunghi are latura 2 şi este de tipul celui din Fig3 (cu baza în sus). Costul pentru celula (3, 2) este 1. În total am obţinut ca impozitul total pentru celula (3, 2) este 3.
Cerinţă
Să se raspundă la M întrebări de forma (x,y): "Care este impozitul care trebuie plătit pentru celula (x,y)?"
Date de intrare
Fişierul de intrare triunghi.in conţine pe prima linie două numere naturale N, respectiv M, separate prin spaţiu, avand semnificaţiile din enunt. Următoarele M conţin câte două numere naturale, x şi y, separate prin spaţiu, reprezentând descrierile celor M întrebări.
Date de ieşire
Fişierul de ieşire triunghi.out
va conţine M linii. Pe linia i se va afişa răspunsul pentru a i-a întrebare din fişierul de intrare.
