Юпитер атакует!
Юпитер наступает! Крупные города разрушены космическими аппаратами Юпитера и человечество наносит ответный удар. Логония возглавляет контрнаступление, взламывая систему управления космическими аппаратами.
В отличие от компьютеров Землян, в которых в байт помещается до 28 возможных значений, компьютеры Юпитера используют байты с B возможными значениями {0, 1, ..., B-1}. Инженеры программного обеспечения Логонии вскрыли технологию микропрограммы космических аппаратов Юпитера и планируют организовать диверсию, в результате которой бы все корабли в конечном итоге самоуничтожились.
В качестве меры безопасности, однако, в космических аппаратах Юпитера работают надзорные программы, периодически проверяющие целостность прошивки путем хеширования его части и сравнения результата с требуемыми значениями. Для хеширования части прошивки в байте с позиции i до байта в позиции j, управляющая программа использует следующую функцию
где P - простое число. Например, если B = 20 и P = 139, а байты от 2 до 5 прошивки имеют значения f_2 = 14, f_3 = 2, f_4 = 2 и f_5 = 4, то
H(f2, ..., 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
Криптологам Логонии необходимо найти способ, чтобы саботировать прошивку без отключения управляющей программы. Первым делом Вас назначили написать программу, имитирующую чередование двух типов команд: редактирование байта прошивки инженерами программного обеспечения Логонии, и вычисление хешей частей прошивки управляющей программы Юпитера. В начале моделирования значение каждого байта в прошивке равно нулю.
Входные данные
Каждый тест задается в нескольких строках. Первая строка содержит четыре целых числа B, P, L и N, где B - количество возможных значений в байте Юпитера, P - модуль хеша Юпитера (2 ≤ B < P ≤ 10^9, P - простое), L - длина (количество байт Юпитера) прошивки космического корабля, N - число команд, которое следует промоделировать (1 ≤ L, N ≤ 10^5). В начале моделирования значение каждого байта прошивки равно f_i = 0 для 1 ≤ i ≤ L. Каждая из следующих N строк задает команду, которую следует промоделировать. Каждая такая команда начинается или с 'E', или с 'H', означающие следующее.
'E' → строка описывает команду редактирования. За буквой следуют два целых числа I и V, означающие что байт в позиции I прошивки (то есть f_I) должен принять значение V (1 ≤ I ≤ L и 0 ≤ V ≤ B - 1).
'H' → строка описывает команду хеширования. За буквой следуют два целых числа I и J, означающие что следует вычислить H(f_I, ..., f_J) (1 ≤ I ≤ J ≤ L).
За последним тестом следует строка из четырех нулей.
Выходные данные
Для каждого теста следует вывести результаты команд хеширования. В i-ой строке вывести целое число, являющееся результатом i-ой команды хеширования. После каждого теста вывести строку из одного символа '-' (дефис).