목성의 공격!

목성이 침공한다! 목성인의 우주선이 주요 도시들을 파괴했고, 인류는 반격에 나섰다. Nlogonia는 우주선의 제어 시스템을 해킹하여 반격을 주도하고 있다. 지구의 컴퓨터에서는 보통 한 바이트가 $2^8$개의 값을 가지지만, 목성의 컴퓨터는 한 바이트가 $B$개의 값 ${0, 1, \dots, B-1}$을 가진다. Nlogonia의 소프트웨어 엔지니어들은 목성 우주선의 펌웨어를 역공학으로 분석했고, 우주선이 결국 자폭하도록 펌웨어를 조작하려 한다.

그러나 보안 장치로서, 각 목성 우주선은 펌웨어의 일부를 해싱하여 그 결과를 알려진 정상 값과 비교함으로써 주기적으로 펌웨어의 무결성을 검사하는 감시 프로그램을 실행한다. 위치 $i$의 바이트부터 위치 $j$의 바이트까지 펌웨어의 일부를 해싱하기 위해, 감시 프로그램은 다음 해시 함수를 사용한다.

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

여기서 $P$는 소수이다. 예를 들어 $B = 20$, $P = 139$이고 펌웨어의 $2$번부터 $5$번 바이트의 값이 $f_2 = 14$, $f_3 = 2$, $f_4 = 2$, $f_5 = 4$라면,

$$ \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} $$

Nlogonia의 암호학자들은 감시 프로그램을 건드리지 않고 펌웨어를 조작할 방법을 찾아야 한다. 그 첫 단계로, 당신은 두 종류의 명령이 섞여 있는 과정을 시뮬레이션하는 프로그램을 작성해야 한다. 하나는 (Nlogonia 엔지니어들이) 펌웨어의 바이트를 수정하는 명령이고, 다른 하나는 (목성 감시 프로그램이) 펌웨어 일부의 해시를 계산하는 명령이다. 시뮬레이션 시작 시 펌웨어의 모든 바이트 값은 $0$이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 네 정수 $B$, $P$, $L$, $N$이 주어진다. $B$는 목성 바이트가 가질 수 있는 값의 개수, $P$는 목성 해시의 법(modulus, $2 \le B < P \le 10^9$이며 $P$는 소수), $L$은 펌웨어의 길이(목성 바이트 개수), $N$은 시뮬레이션할 명령의 개수이다($1 \le L, N \le 10^5$). 각 테스트 케이스가 시작될 때 모든 바이트는 $1 \le i \le L$에 대해 $f_i = 0$이다.

이어지는 $N$개의 줄은 각각 하나의 명령을 나타낸다. 모든 명령은 대문자 E 또는 H로 시작한다.

• E — 수정 명령이며, 뒤에 두 정수 $I$와 $V$가 온다. 위치 $I$의 바이트($f_I$)를 값 $V$로 설정한다($1 \le I \le L$, $0 \le V \le B-1$).
• H — 해시 명령이며, 뒤에 두 정수 $I$와 $J$가 온다. $H(f_I, \dots, f_J)$를 계산한다($1 \le I \le J \le L$).

입력의 마지막에는 0 0 0 0으로 이루어진 줄이 오며, 이 줄은 처리하지 않는다.

각 테스트 케이스에 대해, 모든 해시 명령의 결과를 순서대로 출력한다. $i$번째 줄에는 $i$번째 해시 명령의 결과인 정수를 출력한다. 각 테스트 케이스 뒤에는 하이픈 문자 하나(-)만 있는 줄을 출력한다.