Юпитер наступает! Крупные города разрушены космическими аппаратами Юпитера и человечество наносит ответный удар. Логония возглавляет контрнаступление, взламывая систему управления космическими аппаратами. В отличие от компьютеров Землян, в которых в байт помещается до \textbf{28} возможных значений, компьютеры Юпитера используют байты с \textbf{B }возможными значениями \textbf{\{0, 1, ..., B-1\}}. Инженеры программного обеспечения Логонии вскрыли технологию микропрограммы космических аппаратов Юпитера и планируют организовать диверсию, в результате которой бы все корабли в конечном итоге самоуничтожились. В качестве меры безопасности, однако, в космических аппаратах Юпитера работают надзорные программы, периодически проверяющие целостность прошивки путем хеширования его части и сравнения результата с требуемыми значениями. Для хеширования части прошивки в байте с позиции \textbf{i} до байта в позиции \textbf{j}, управляющая программа использует следующую функцию \includegraphics{https://static.e-olymp.com/content/a3/a330686dbf85d0929177a273bafceee912393a91.jpg} где \textbf{P} - простое число. Например, если \textbf{B = 20} и \textbf{P = 139}, а байты от \textbf{2} до \textbf{5} прошивки имеют значения \textbf{f_2 = 14}, \textbf{f_3 = 2}, \textbf{f_4 = 2} и \textbf{f_5 = 4}, то \textbf{H(f2, ..., f_5) = B^0f_5 + B^1f_4 + B^2f_3 + B^3f_2 (mod P)} \textbf{= 20^0×4 + 20^1×2 + 20^2×2 + 20^3×14 (mod 139)} \textbf{= 4 + 40 + 800 + 112000 (mod 139)} \textbf{= 112844 (mod 139)} \textbf{= 115} Криптологам Логонии необходимо найти способ, чтобы саботировать прошивку без отключения управляющей программы. Первым делом Вас назначили написать программу, имитирующую чередование двух типов команд: редактирование байта прошивки инженерами программного обеспечения Логонии, и вычисление хешей частей прошивки управляющей программы Юпитера. В начале моделирования значение каждого байта в прошивке равно нулю. \InputFile Каждый тест задается в нескольких строках. Первая строка содержит четыре целых числа \textbf{B}, \textbf{P}, \textbf{L }и\textbf{ N}, где \textbf{B} - количество возможных значений в байте Юпитера, \textbf{P} - модуль хеша Юпитера (\textbf{2 }≤ \textbf{B }< \textbf{P }≤ \textbf{10^9}, \textbf{P} - простое), \textbf{L }- длина (количество байт Юпитера) прошивки космического корабля, \textbf{N} - число команд, которое следует промоделировать (\textbf{1 }≤ \textbf{L}, \textbf{N }≤ \textbf{10^5}). В начале моделирования значение каждого байта прошивки равно \textbf{f_i = 0 }для \textbf{1 }≤ \textbf{i }≤ \textbf{L}. Каждая из следующих \textbf{N} строк задает команду, которую следует промоделировать. Каждая такая команда начинается или с '\textbf{E}', или с '\textbf{H}', означающие следующее. '\textbf{E}' → строка описывает команду редактирования. За буквой следуют два целых числа \textbf{I }и \textbf{V}, означающие что байт в позиции \textbf{I} прошивки (то есть \textbf{f_I}) должен принять значение \textbf{V }(\textbf{1 }≤ \textbf{I }≤ \textbf{L }и \textbf{0 }≤ \textbf{V }≤ \textbf{B - 1}). '\textbf{H}' → строка описывает команду хеширования. За буквой следуют два целых числа \textbf{I }и \textbf{J}, означающие что следует вычислить \textbf{H(f_I, ..., f_J) }(\textbf{1 }≤ \textbf{I }≤ \textbf{J} ≤ \textbf{L}). За последним тестом следует строка из четырех нулей. \OutputFile Для каждого теста следует вывести результаты команд хеширования. В \textbf{i}-ой строке вывести целое число, являющееся результатом \textbf{i}-ой команды хеширования. После каждого теста вывести строку из одного символа '\textbf{-}' (дефис).