sea

Cerință

Pe mare se află $N$ vapoare. Malul este în mod curios perfect drept şi este reprezentat prin axa Ox a sistemului de coordonate. Cele N vapoare sunt reprezentate prin perechi de coordonate $(V_{x_i}, V_{y_i})$, unde $V_{y_i}$ este strict pozitiv (marea este deasupra axei Ox). Pe mal se află $M$ faruri, date prin coordonatele lor $F_{x_i}$ (fiind exact la limita dintre mare şi uscat, $y$-ul lor este întotdeauna $0$). Cele $M$ faruri sunt ciudate pentru că ele nu pot lumina decât în stânga. Astfel aria luminată de fiecare far $i$ este delimitată de un sfert de cerc cu o rază $F_{r_i}$. Mai exact, un vapor este luminat de un anumit far dacă se află în stânga farului (are $x$-ul mai mic) şi distanţa de la far la vapor este mai mică sau egală cu valoarea $F_{r_i}$ asociată farului respectiv.
Pentru fiecare far se mai dă şi un număr natural strict pozitiv $F_{n_i}$. Din motive greu de înţeles, şeful portului doreşte ca fiecare far $i$ să lumineze cel puţin $F_{n_i}$ vapoare (un vapor poate fi luminat de mai multe faruri). El doreşte consum minim de energie şi vrea să afle pentru fiecare far raza minimă necesară pentru a lumina numărul cerut de vapoare.

Determinaţi pentru fiecare far valoarea $F_{r_i}$ care reprezintă raza minimă necesară pentru ca farul să lumineze cel puţin $F_{n_i}$ vapoare.

Date de intrare

Prima linie a fişierului sea.in conţine două numere întregi $N$ şi $M$ separate printr-un spaţiu, reprezentând numărul de vapoare, respectiv numărul de faruri. Fiecare dintre următoarele $N$ linii conţine câte o pereche de numere reale separate printr-un spaţiu $V_{x_i}$ şi $V_{y_i}$ (coordonatele vapoarelor). Fiecare dintre următoarele $M$ linii conţine câte o pereche de numere separate printr-un spaţiu, unul real $F_{x_i}$ şi unul întreg $F_{n_i}$ (coordonatele orizontale şi numerele asociate farurilor).

Date de ieșire

Fişierul sea.out va conţine $M$ linii, fiecare linie conţinând un număr real, dat cu $4$ zecimale: pe linia $i$ se află raza minimă necesară pentru ca farul $i$ să lumineze $F_{n_i}$ vapoare.

Restricții și precizări

• $1 \leq N \leq 400$
• $1 \leq M \leq 100 \ 000$
• $0 < y, r < 100 \ 000$
• $-100 \ 000 < x < 100 \ 000$
• $1 \leq F_{n_i} \leq N$
• În fişierul de intrare farurile sunt sortate crescător după coordonatele $x$.
• Nu vor exista două vapoare, sau un far şi un vapor cu acelaşi $x$. În schimb pot exista două sau mai multe faruri cu acelaşi $x$, caz în care ele vor fi unul lângă altul în fişierul de intrare (evident din moment ce sunt sortate după $x$). Ordinea în care apar în fişierul de intrare farurile cu acelaşi $x$ nu este definită. Pot exista chiar două faruri identice.
• Numerele reale din fişierul de intrare vor avea maxim $4$ zecimale
• Rezultatul va fi verificat cu o precizie de $0.001$ (rezultatul va fi considerat corect dacă modulul diferenţei dintre rezultatul corect şi cel furnizat de concurent nu depăşeşte $0.001$)
• Există întotdeauna soluţie (pentru fiecare far $i$ vor exista întotdeauna cel puţin $F_{n_i}$ vapoare în stânga lui).

Exemplu

sea.in

3 5
-0.5 0.5
-2 5
3 4
-1 1
0 1
0 2
0 1
5 1

sea.out

5.0990
0.7071
5.3852
0.7071
4.4721