Jupiter is invading! Major cities have been destroyed by Jovian spacecrafts and humanity is ghting back. Nlogonia is spearheading the counter-oensive, by hacking into the spacecrafts' control system. Unlike Earthling computers, in which usually a byte has \textbf{28} possible values, Jovian computers use bytes with \textbf{B} possible values, \textbf{\{0, 1, ..., B-1\}}. Nlogonian software engineers have reverse-engineered the rmware for the Jovian spacecrafts, and plan to sabotage it so that the ships eventually selfdestruct. As a security measure, however, the Jovian spacecrafts run a supervisory program that periodically checks the integrity of the rmware, by hashing portions of it and comparing the result against known good values. To hash the portion of the rmware from the byte at position \textbf{i} to the byte at position \textbf{j}, the supervisor uses the hash function \includegraphics{https://static.e-olymp.com/content/a3/a330686dbf85d0929177a273bafceee912393a91.jpg} where \textbf{P} is a prime number. For instance, if \textbf{B = 20} and \textbf{P = 139}, while bytes \textbf{2} to \textbf{5} of the firmware have the values \textbf{f_2 = 14}, \textbf{f_3 = 2}, \textbf{f_4 = 2}, and \textbf{f_5 = 4}, then \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} The Nlogonian cryptologists need to find a way to sabotage the rmware without tripping the supervisor. As a first step, you have been assigned to write a program to simulate the interleaving of two types of commands: editing bytes of the rmware by the Nlogonian software engineers, and computing hashes of portions of the firmware by the Jovian supervisory program. At the beginning of the simulation the value of every byte in the firmware is zero. \InputFile Each test case is described using several lines. The first line contains four integers \textbf{B}, \textbf{P}, \textbf{L} and \textbf{N}, where \textbf{B} is the number of possible values of a Jovian byte, \textbf{P} is the modulus of the Jovian hash (\textbf{2} ≤ \textbf{B} < \textbf{P} ≤ \textbf{10^9} and \textbf{P} prime), \textbf{L} is the length (number of Jovian bytes) of the spacecrafts' firmware, and \textbf{N} is the number of commands to simulate (\textbf{1} ≤ \textbf{L}, \textbf{N} ≤ \textbf{10^5}). At the beginning of the simulation the value of every byte in the firmware is \textbf{f_i = 0} for \textbf{1} ≤ \textbf{i} ≤ \textbf{L}. Each of the next \textbf{N} lines describes a command to simulate. Each command description starts with an uppercase letter that is either '\textbf{E}' or '\textbf{H}', with the following meanings. '\textbf{E}' → The line describes an edit command. The letter is followed by two integers \textbf{I} and \textbf{V} indicating that the byte at position \textbf{I} of the firmware (that is, \textbf{f_I}) must receive the value \textbf{V} (\textbf{1} ≤ \textbf{I} ≤ \textbf{L} and \textbf{0} ≤ \textbf{V} ≤ \textbf{B-1}). '\textbf{H}' → The line describes a hash command. The letter is followed by two integers \textbf{I} and \textbf{J} indicating that \textbf{H(f_I, ..., f_J) }must be computed (\textbf{1} ≤ \textbf{I} ≤ \textbf{J} ≤ \textbf{L}). The last test case is followed by a line containing four zeros. \OutputFile For each test case output the results of the hash commands in the input. In the \textbf{i}-th line write an integer representing the result of the \textbf{i}-th hash command. Print a line containing a single character '\textbf{-}' (hyphen) after each test case.