Юпітер атакує!#5749
На відміну від комп'ютерів Землян, де байт зазвичай має можливих значень, комп'ютери Юпітера використовують байти з можливими значеннями \{0, 1, \ldots, B-1\}. Інженери програмного забезпечення Логонії розкрили технологію мікропрограми космічних апаратів Юпітера і планують організувати диверсію, в результаті якої всі кораблі в кінцевому підсумку самознищилися б.
Юпітер наступає! Великі міста зруйновані космічними апаратами Юпітера, і людство завдає удару у відповідь. Логонія очолює контрнаступ, зламуючи систему управління космічними апаратами.
Як міра безпеки, однак, у космічних апаратах Юпітера працюють наглядові програми, які періодично перевіряють цілісність прошивки шляхом хешування її частини і порівняння результату з потрібними значеннями. Для хешування частини прошивки з байта в позиції до байта в позиції , керуюча програма використовує наступну функцію
де — просте число. Наприклад, якщо B = 20 та P = 139, а байти від до прошивки мають значення f_2 = 14, f_3 = 2, f_4 = 2 і f_5 = 4, то
Криптологам Логонії необхідно знайти спосіб, щоб саботувати прошивку без відключення керуючої програми. Першим ділом вас призначили написати програму, що імітує чергування двох типів команд: редагування байта прошивки інженерами програмного забезпечення Логонії і обчислення хешів частин прошивки керуючою програмою Юпітера. На початку моделювання значення кожного байта в прошивці дорівнює нулю.
Кожен тест задається в кількох рядках. Перший рядок містить чотири цілі числа , , і , де — кількість можливих значень у байті Юпітера, — модуль хеша Юпітера (2 \leq B < P \leq 10^9, — просте), — довжина (кількість байтів Юпітера) прошивки космічного корабля, — число команд, які слід промоделювати (1 \leq L, N \leq 10^5). На початку моделювання значення кожного байта прошивки дорівнює f_i = 0 для 1 \leq i \leq L. Кожен з наступних рядків задає команду, яку слід промоделювати. Кожна така команда починається із заголовної літери 'E' або 'H', що означає наступне:
'E' Рядок описує команду редагування. За літерою слідують два цілих числа і , що означає, що байт у позиції прошивки (f_I) повинен прийняти значення (1 \leq I \leq L, 0 \leq V \leq B - 1).
'H' Рядок описує команду хешування. За літерою слідують два цілих числа і , що означає, що необхідно обчислити H(f_I, \ldots, f_J) (1 \leq I \leq J \leq L).
За останнім тестом слідує рядок із чотирьох нулів.
Для кожного тесту слід вивести результати команд хешування. У -му рядку вивести ціле число, яке є результатом -ї команди хешування. Після кожного тесту вивести рядок з одного символу '-' (дефіс).
Приклад 1