Jupiter Attacks!

Time limit1sMemory limit128 MB

Summary

Maintain an array under point updates and queries of a polynomial hash over a subarray modulo a prime, printing each hash result.

Level: Medium7 of 10
Topics: Segment tree, Prefix sum, Math, Implementation
Solved: No attempts yet

Problem

Jupiter is invading! Major cities have been destroyed by Jovian spacecraft, and humanity is fighting back. Nlogonia is spearheading the counter-offensive by hacking into the spacecraft's control systems. Unlike Earthling computers, in which a byte usually has $2^8$ possible values, Jovian computers use bytes with $B$ possible values, $\{0, 1, \dots, B-1\}$ . Nlogonian software engineers have reverse-engineered the firmware of the Jovian spacecraft and plan to sabotage it so that the ships eventually self-destruct.

As a security measure, however, each Jovian spacecraft runs a supervisory program that periodically checks the integrity of the firmware by hashing portions of it and comparing the result against known-good values. To hash the portion of the firmware from the byte at position $i$ to the byte at position $j$ , the supervisor uses the hash function

$H(f_i, \dots, f_j) = \left(\sum_{k=0}^{j-i} B^k f_{j-k}\right) \bmod P$

where $P$ is a prime number. For instance, if $B = 20$ and $P = 139$ , and bytes $2$ to $5$ of the firmware have the values $f_2 = 14$ , $f_3 = 2$ , $f_4 = 2$ , and $f_5 = 4$ , then

\begin{aligned} H(f_2, \dots, f_5) &= B^0 f_5 + B^1 f_4 + B^2 f_3 + B^3 f_2 \pmod P \\ &= 20^0 \cdot 4 + 20^1 \cdot 2 + 20^2 \cdot 2 + 20^3 \cdot 14 \pmod{139} \\ &= 4 + 40 + 800 + 112000 \pmod{139} \\ &= 112844 \pmod{139} \\ &= 115. \end{aligned}

The Nlogonian cryptologists need a way to sabotage the firmware without tripping the supervisor. As a first step, you must write a program that simulates an interleaving of two kinds of commands: editing bytes of the firmware (by the Nlogonian software engineers) and computing hashes of portions of the firmware (by the Jovian supervisory program). At the beginning of the simulation, every byte of the firmware is zero.

Input

The input consists of several test cases. Each test case begins with a line containing four integers $B$ , $P$ , $L$ , and $N$ : $B$ is the number of possible values of a Jovian byte, $P$ is the modulus of the Jovian hash ( $2 \le B < P \le 10^9$ , with $P$ prime), $L$ is the length of the firmware in Jovian bytes, and $N$ is the number of commands to simulate ( $1 \le L, N \le 10^5$ ). At the start of each test case, every byte is $f_i = 0$ for $1 \le i \le L$ .

Each of the next $N$ lines describes one command. Every command starts with an uppercase letter, either E or H.

E — an edit command, followed by two integers $I$ and $V$ , meaning that the byte at position $I$ (that is, $f_I$ ) must be set to the value $V$ ( $1 \le I \le L$ and $0 \le V \le B-1$ ).
H — a hash command, followed by two integers $I$ and $J$ , meaning that $H(f_I, \dots, f_J)$ must be computed ( $1 \le I \le J \le L$ ).

The input ends with a line containing 0 0 0 0, which must not be processed.

Output

For each test case, output the result of every hash command, in order: on the $i$ -th line, print an integer, the result of the $i$ -th hash command. After each test case, print a line containing a single character - (a hyphen).

Examples1

Example 1

Input

20 139 5 7
E 1 12
E 2 14
E 3 2
E 4 2
E 5 4
H 2 5
E 2 14
10 1000003 6 11
E 1 3
E 2 4
E 3 5
E 4 6
E 5 7
E 6 8
H 1 6
E 3 0
E 3 9
H 1 3
H 4 6
999999935 999999937 100000 7
E 100000 6
E 1 7
H 1 100000
E 50000 8
H 1 100000
H 25000 75000
H 23987 23987
0 0 0 0

Expected output