Geri çəkmə
Tennis topları ilə jonglyorluq etmək yalnız ürək-əzələ sistemini gücləndirmir və ruh tarazlığını sabitləmir, həm də davamlı məlumat strukturlarını dinamik modelləşdirməyə kömək edir...
(Sergey Kopelioviç - mühazirə zamanı deyilməmişdən)
Sergey böyük bir şirkətdə sistem administratoru olaraq çalışır. Onun vəzifələrinə müxtəlif serverlərdə saxlanılan məlumatların ehtiyat nüsxəsini çıxarmaq və problem yaranarsa əvvəlki versiyaya "geri qaytarmaq" daxildir.
Hal-hazırda Sergey məlumatların bərpası üçün saxlama yerinin çatışmazlığı problemi ilə üzləşir. O, məlumatların bir hissəsini yeni serverlərə köçürməyə qərar verib. Təəssüf ki, köçürmə zamanı bir problem yaranarsa, geri qaytarma mümkün olmayacaq, buna görə də köçürmə prosesi diqqətlə planlaşdırılmalıdır.
Sergey hazırda müxtəlif serverlərin n bərpa nöqtəsini saxlayır, bunlar 1-dən n-ə qədər nömrələnib. i nömrəli bərpa nöqtəsi a_i serveri üçün geri qaytarma etməyə imkan verir. Sergey köçürməni mərhələlərə bölməyə qərar verib, belə ki, hər mərhələdə problem yaranarsa, l, l + 1, ..., r nömrəli bərpa nöqtələri mövcud olacaq.
Məlumatların köçürülməsini optimal şəkildə planlaşdırmaq üçün Sergey sorğulara cavab verməyi öyrənməlidir: verilmiş l üçün, köçürmə prosesində ən azı k müxtəlif serverlərin bərpa nöqtələrinin mövcud olacağı minimum r nədir.
Sergeyə kömək edin.
Giriş verilənləri
Giriş faylının birinci sətiri boşluqlarla ayrılmış iki tam ədəd n və m - bərpa nöqtələrinin sayı və serverlərin sayı (1 ≤ n, m ≤ 100000) ehtiva edir. İkinci sətir n tam ədəd a_1, a_2, ..., a_n - bərpa nöqtələrinə uyğun serverlərin nömrələrini (1 ≤ a_i ≤ m) ehtiva edir.
Giriş faylının üçüncü sətiri işlənməli olan sorğuların sayını q ehtiva edir (1 ≤ q ≤ 100000). Sorğuların işlənməsi zamanı p sayını saxlamaq lazımdır, başlanğıcda 0-a bərabərdir. Hər bir sorğu x_i və y_i cütü ilə verilir, sorğu məlumatlarını aşağıdakı kimi əldə edin:
l_i = ((x_i + p) mod n) + 1, k_i = ((y_i + p) mod m) + 1 (1 ≤ l_i, x_i ≤ n, 1 ≤ k_i, y_i ≤ m).
Qoy i-ci sorğunun cavabı r olsun. Bu sorğu yerinə yetirildikdən sonra p dəyərini r olaraq təyin edin.
Çıxış verilənləri
Hər bir sorğu üçün bir ədəd çıxarın - axtarılan minimum r, əgər belə bir r yoxdursa, 0.