eolymp
bolt
Try our new interface for solving problems
Məsələlər

Homer Simpsonun çəlləkləri

Homer Simpsonun çəlləkləri

Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Homer Simpsonun müxtəlif mayelər üçün çəlləkləri var. Məsələn, su çəlləyi, neft çəlləyi və s. O, çəlləkləri evinin zirzəmisində müəyyən sıra ilə saxlayır.

Hər bir çəlləyin öz həcmi var və hər bir çəlləyə yalnız öz tutumu qədər maye tökmək olar.

i-ci çəlləyin tutumu Cap[i] ilə işarə edək. Zirzəmidə N çəllək var və çəlləklərin sıra nömrəsi 1-dən başlayır. Beləki, 1-ci çəlləyin həcmi Cap[1],..., n-ci çəlləyin həcmi Cap[N]-dir.

Son vaxtlar Homerin oğlu Bart bazardan müxtəlif mayelər oğurlamağa başlayıb. O müxtəlif mayelər, su, yağ, qatıq və sair oğurlayır.

Hər gün Bart evə həcmi v olan l mayesi ilə gəlir. Homer buna qarşı deyil, çünki Homerin qaydalarına görə pulsuz olan hər şey qəbul ediləndir. Homer Bartın gətirdiyi mayeləri uyğun çəlləyə tökür. Mayeləri çəlləyə tökən zaman o “Simpson Çəllək Axtarma Alqoritmi” adlandırdığı strategiyanı istifadə edir. Alqoritm aşağıdakı kimidir:

İlk olaraq Homer boş olan hissəsi >=v olan bütün çəlləkləri müəyyənləşdirir (ilk olaraq bütün çəlləklərin boş qalan hissəsi onların həcminə bərabərdir). Bundan sonra əgər bir neçə seçim varsa, o ən az boş hissəsi olan çəlləyi müəyyənləşdirir. Əgər yenidən bir neçə eyni seçim olarsa, Homer ən kiçik indeksi olan çəlləyi seçir.

Deyək ki, Homer alqoritmə uyğun indeksi b olan çəlləyi seçib. Onda Homer və Bart gətirdiyi mayeni b-ci çəlləyə tökürlər. Bunun nəticəsində b-ci çəlləyin həcmi v qədər azalır.

Giriş verilənləri

Birinci sətirdə 3 tam ədəd var: zirzəmidəki çəlləklərin sayı (N) (1<=N<=1000000), L – maye növlərinin sayı (1<=L<=1000), q – Bartın mağazadan oğurluq etdiyi günlərin sayı (sorğuların sayı 1<=q<=100000).

Növbəti sətirdə N sayda tam ədəd var. i-cı ədəd çəlləyin Cap[i] həcminə bərabərdir. Çəlləyin ilkin olaraq boşdur. (1<=Cap[i]<=10^9).

Növbəti sətir n tam ədər ehtiva edir. Sətirdəki i-ci ədəd müəyyən l ədədinə bərabərdir. l mayenin növünü (yağ, su, sabun, qatıq və s.) göstərir (1<=l<=L).

Növbət q sayda sətir sorğuları ehtiva edir. i-ci sorğu boşluq ilə ayrılmış lv ədədlərini ehtiva edir (1<=l<=L, 1<=v<=10^9).

Çıxış verilənləri

Hər bir sorğu üçün ayrı bir sətirdə Homerin alqoritminə əsasən müəyyən olunmuş barelin indeksini b-ni (1<=b<=N) vermək tələb olunur. Nəzərə alın ki, alqoritm öz işini bitirdikdən sonra mayeyə uyğun qalan çəlləklərdə boş yer qalmayıbsa, Homer və Bart yerdə qalan mayeni kənara atırlar. Bu zaman nəticə olaraq -1 göstərmək lazımdır.

Nümunə

Giriş verilənləri #1
3 2 9
400 100 600
1 2 1
1 500
1 200
1 50
2 50
1 300
1 199
1 51
2 51
2 50
Çıxış verilənləri #1
3
1
3
2
-1
1
-1
-1
2
Mənbə 2014 Azerbaijan - Zadeh cup