Möcüzəvi dərman

Cey biotibbi tədqiqatlara böyük maraq göstərir və o, təhlükəli bir xəstəliyə qarşı dərman tapmağa çox yaxındır. Bu dərmanı hazırlamaq üçün xüsusi bir fermentə ehtiyacı var. Bu ferment kifayət qədər bahalıdır və təəssüf ki, müəyyən bir müddətdən sonra təsirini itirir. Hazırda Cey klinik sınaq mərhələsindədir və hər saat bu preparata ehtiyacı var. Bu o deməkdir ki, hər saat eyni miqdarda preparat hazırlamalıdır. Fermentin qiyməti saatdan saata dəyişə bilər və saat i-dəki qiyməti c[i] ilə ifadə olunur. Fermentin ömrü h saatdır. Cey, növbəti n saat ərzində fermentin qiymətlərini bilir və dərmanın hər bir n saatda əlçatan olması üçün fermenti ən uyğun qiymətə necə ala biləcəyini tapmalıdır. Eyni qiymət olduqda, Cey daha təzə ferment almağa üstünlük verir və onu ehtiyatda saxlamır. Hər saat fermentin məhdudiyyətsiz miqdarda alınması mümkündür. Ona bu məsələdə kömək edə bilərsinizmi?

Giriş məlumatları

Bir neçə testdən ibarətdir. Hər bir test saatların sayı n (n < 10000) ilə başlayır. Daha sonra fermentin ömrü h (h < 10000), tədqiqat intervalının başlanğıc b və son e nöqtələri (1 ≤ b, e ≤ n) və fermentin qiyməti c[i] (c[i] < 10000), i = 1 .. n verilir.

Çıxış məlumatları

Hər bir [b, e] intervalı üçün Ceyin almalı olduğu fermentlərin sayını çıxarın. Çıxarılan rəqəmləri tabulyasiya simvolları ilə ayırmaq lazımdır.

Misalda iki test verilib. Birinci test üçün n = 6, h = 3, b = 1, e = 6, qiymətlər müvafiq olaraq 5 4 4 3 5 6. Hər saat üçün alınan fermentlərin sayını sətirin əvvəlindən başlayaraq tabulyasiya simvolları ilə ayıraraq çıxarmaq lazımdır.