14071번 - Rudar 다국어

Pod rudarske špilje zamišljamo kao izlomljenu liniju u koordinatnom sustavu koja se sastoji od n + 1 vrhova (x₀, y₀), (x₁, y₁), . . . , (x_n, y_n) te n dužina koje povezuju uzastopne vrhove. Pod počinje u ishodištu, proteže se slijeva nadesno te završava na x-osi (0 = x₀ < x₁ < . . . < x_n, y₀ = y_n = 0). Dužina koja povezuje vrh (x_i−1 , y_i−1) sa vrhom (x_i , y_i) je opisana sa dva cijela broja d_i i k_i — redom duljinom projekcije dužine na x-os te koeficijentom smjera pravca odredenog dužinom. Dakle, točka (x_i , y_i) je jednaka (x_i−1 + d_i , y_i−1 + k_id_i).

Ilustracije primjera test podataka

Rudari mogu objesiti lampu u bilo koju točku A iznad poda špilje. Kažemo da lampa osvjetljava točku B na podu špilje ako dužina AB ne siječe pod špilje (dozvoljeno je da dužina AB dodiruje pod špilje u točkama ili uzduž segmenata). Jasno je da lampa osvjetljava točku A 0 koja se nalazi na podu špilje neposredno ispod A. Glavni interval lampe u točki A je područje poda špilje do kojeg rudari mogu doći šetnjom po podu špilje počevši iz točke A 0 , a da cijelo vrijeme budu osvijetljeni lampom u točki A.

Zadano je q mogućih pozicija lampe. Za svaku poziciju odredite lijevi i desni rub glavnog intervala lampe na toj poziciji.

U prvom redu nalaze se prirodni brojevi n i q (1 ≤ n, q ≤ 100 000) — broj segmenata od kojih se sastoji pod špilje te broj mogućih pozicija lampe.

U i-tom od sljedećih n redova nalaze se dva cijela broja d_i i k_i (1 ≤ d_i ≤ 10⁹ , −10⁹ ≤ k_i ≤ 10⁹ ) — duljina projekcije i koeficijent smjera i-tog segmenta. Možete pretpostaviti da su parametri takvi da za vrhove poda špilje vrijedi 0 = x₀ < x₁ < . . . < x_n ≤ 10⁹ , y₀ = y_n = 0, −10⁹ ≤ y_i ≤ 10⁹ .

U i-tom od sljedećih q redova nalaze se dva cijela broja x'_i , y'_i (0 ≤ x'_i ≤ x_n, −10⁹ ≤ y'_i ≤ 10⁹) — koordinate i-te potencijalne pozicije. Sve pozicije se nalaze strogo iznad poda špilje.

Ispišite q redova. U i-ti red ispišite dva cijela broja — redom x-koordinate lijevog i desnog ruba glavnog intervala lampe u i-toj potencijalnoj poziciji. Možete pretpostaviti da su tražene koordinate uvijek cijeli brojevi.