Yupiter hücum edir!#5749
Yupiter hücum edir! Böyük şəhərlər Yupiterin kosmik aparatları tərəfindən dağıdılıb və insanlıq əks-hücum edir. Logoniya bu əks-hücumu idarə edir, kosmik aparatların idarəetmə sistemini sındıraraq.
Yer kürəsinin kompüterlərindən fərqli olaraq, Yupiterin kompüterləri bir baytda B mümkün dəyər yerləşdirə bilir və bu dəyərlər {0, 1, ..., B-1} aralığında olur. Logoniya proqram mühəndisləri Yupiterin kosmik aparatlarının mikroproqram texnologiyasını sındırıb və bütün gəmilərin nəticədə öz-özünü məhv etməsi üçün diversiya təşkil etməyi planlaşdırırlar.
Lakin, təhlükəsizlik tədbiri olaraq, Yupiterin kosmik aparatlarında nəzarət proqramları işləyir, periodik olaraq proqram təminatının bütövlüyünü yoxlayaraq onun bir hissəsini həşləyir və nəticəni tələb olunan dəyərlərlə müqayisə edir. Proqram təminatının baytının i mövqeyindən j mövqeyinə qədər olan hissəsini həşləmək üçün idarəetmə proqramı aşağıdakı funksiyanı istifadə edir:
burada P - sadə ədəddir. Məsələn, əgər B = 20 və P = 139, və proqram təminatının 2 ilə 5 arası baytları f_2 = 14, f_3 = 2, f_4 = 2 və f_5 = 4 dəyərlərinə malikdirsə, onda
H(f_2, ..., f_5) = B^0f_5 + B^1f_4 + B^2f_3 + B^3f_2 (mod P)
= 20^0×4 + 20^1×2 + 20^2×2 + 20^3×14 (mod 139)
= 4 + 40 + 800 + 112000 (mod 139)
= 112844 (mod 139)
= 115
Logoniya kriptoqrafları proqram təminatını idarəetmə proqramını söndürmədən sabotaj etmək üçün bir yol tapmalıdırlar. İlk növbədə sizə Logoniya proqram mühəndislərinin proqram təminatının baytını redaktə etmə əmrləri və Yupiterin idarəetmə proqramının proqram təminatının hissələrinin həşlənməsi əmrlərinin növbələşməsini təqlid edən bir proqram yazmaq tapşırılıb. Simulyasiyanın əvvəlində proqram təminatının hər bir baytının dəyəri sıfıra bərabərdir.
Hər bir test bir neçə sətirdə verilir. İlk sətir dörd tam ədəd B, P, L və N ehtiva edir, burada B - Yupiterin baytında mümkün olan dəyərlərin sayı, P - Yupiterin həş modulu (2 ≤ B < P ≤ 10^9, P - sadə), L - kosmik gəminin proqram təminatının uzunluğu (Yupiterin baytlarının sayı), N - simulyasiya olunacaq əmrlərin sayı (1 ≤ L, N ≤ 10^5). Simulyasiyanın əvvəlində proqram təminatının hər bir baytının dəyəri f_i = 0 üçün 1 ≤ i ≤ L. Növbəti N sətirdən hər biri simulyasiya olunacaq əmri təyin edir. Hər belə əmr ya 'E', ya da 'H' ilə başlayır, aşağıdakıları ifadə edir.
'E' → sətir redaktə əmri təsvir edir. Hərfdən sonra iki tam ədəd I və V gəlir, bu da proqram təminatının I mövqeyindəki baytın (yəni f_I) V dəyərini almalı olduğunu ifadə edir (1 ≤ I ≤ L və 0 ≤ V ≤ B - 1).
'H' → sətir həşləmə əmri təsvir edir. Hərfdən sonra iki tam ədəd I və J gəlir, bu da H(f_I, ..., f_J) hesablanmalı olduğunu ifadə edir (1 ≤ I ≤ J ≤ L).
Son testdən sonra dörd sıfırdan ibarət bir sətir gəlir.
Hər bir test üçün həşləmə əmrlərinin nəticələrini çıxış edin. i-ci sətirdə i-ci həşləmə əmri nəticəsi olan tam ədədi çıxış edin. Hər testdən sonra bir '-' (defis) simvolundan ibarət bir sətir çıxış edin.
Nümunə 1