Qar çəkmələri (Qızıl)
Fermada qış mövsümüdür və çox qar yağıb. Fermadan anbara gedən yolda ardıcıl nömrələnmiş n hissə var və i-ci hissə f[i] fut qarla örtülüb.
FD-nin zirzəmisində b cüt çəkmə var, 1..b nömrələnmiş. Bəzi çəkmələr daha ağır, bəziləri isə daha yüngüldür. i cütü FD-yə maksimum s[i] fut dərinliyində qarda və maksimum d[i] uzunluğunda addım atmağa imkan verir.
FD 1-ci hissədən başlayır və inəkləri oyatmaq üçün n-ci hissəyə çatmalıdır. 1-ci hissə fermanın damı ilə, n-ci hissə isə anbarın damı ilə qorunur, buna görə də onların üzərində qar yoxdur. FD-yə fermadan anbara keçmək üçün hansı çəkməni geyinməli olduğunu müəyyən etməyə kömək edin.
Giriş məlumatları
Birinci sətir iki tam ədəd n və b (1 ≤ n, b ≤ 10^5) ehtiva edir.
İkinci sətir n tam ədəd ehtiva edir. i-ci ədəd f[i] - i-ci hissədə qarın dərinliyidir (0 ≤ f[i] ≤ 10^9). Zəmanət verilir ki, f[1] = f[n] = 0.
Növbəti b sətirin hər biri iki tam ədəd ehtiva edir. Birinci tam ədəd s[i] - i cütü üçün maksimum qar dərinliyidir. İkinci tam ədəd d[i] - i cütü üçün maksimum addım ölçüsüdür. Zəmanət verilir ki, 0 ≤ s[i] ≤ 10^9 və 1 ≤ d[i] ≤ n − 1.
Çıxış məlumatları
Çıxış b sətirdən ibarət olmalıdır. i-ci sətir bir tam ədəd 1 ehtiva etməlidir, əgər FD i-ci cüt çəkməni geyinərək 1-ci hissədən n-ci hissəyə keçə bilirsə, və 0 əks halda.