게바이트의 고행

해마다 봄이면 그랬듯이, 위쳐 게바이트는 이번에도 길을 떠나 위쳐의 일을 맛보고 가는 길에 돈을 벌려고 한다. 길은 서쪽에서 동쪽으로 $n$ 마일 뻗어 있다. 마일마다 다음 세 종류 가운데 하나의 대상이 기다린다.

• B $b_i$: 지역 농민들이 공포에 떠는 잔혹한 짐승의 굴이다. 게바이트가 굴에 들어서면 짐승이 즉시 달려들어 위쳐에게 상처를 입힌다. 첫 공격을 버텨내면 그는 은검을 뽑아 짐승을 죽인다. 체력은 다음과 같이 바뀐다: $\text{if } H \leq b_i \text{ then } death \text{ else } H := H - b_i\text{.}$
• K $k_i$: 게바이트가 술을 좋아해서 반드시 들르는 지역 여관이다. 체력이 $k_i$ 미만인 상태로 주점에 머물면, 술을 한 통 더 마셔 새벽 전에 죽는다. 그렇지 않으면 심한 숙취와 함께 체력이 $k_i$로 떨어지고, 그는 여정을 이어 간다. 체력은 다음과 같이 바뀐다: $\text{if } H < k_i \text{ then } death \text{ else } H := k_i\text{.}$
• C $c_i$: 강력한 마녀의 집이다. 마녀의 마법과 탕약은 상처를 치료하고 숙취를 없앤다. 체력이 $c_i$ 미만인 상태로 게바이트가 마녀를 만나면, 마녀의 주문과 달인 약으로 체력이 $c_i$까지 오른다. 체력은 다음과 같이 바뀐다: $H := max(H, c_i)\text{.}$

날이 지나면서 $i$일째에는 다음 두 가지 중 하나가 일어난다.

• 길 위의 대상 하나가 바뀐다. 예를 들어 마녀의 집을 지역 상인이 사들여 주점으로 바꾸거나, 지하 세계에서 새로운 짐승이 기어 나와 여관을 불태우고 그 자리에 굴을 판다.
• 게바이트가 집 밖으로 나가 나무 아래 앉아, $i$번째 대상에서 출발해 동쪽으로 가면 목숨을 잃지 않고 어디까지 갈 수 있을지 생각한다. 그는 신비한 코딩 마법으로 알려진 마법사인 당신에게 이 질문들에 답해 달라고 부탁한다.

길의 변경은 영구히 남는다. 각 질문은 서로 독립이며, 어느 질문에서든 게바이트는 체력 $H$에서 출발한다. 위쳐는 무엇을 할지 생각만 할 뿐, 실제로 길을 떠나지는 않는다.

입력의 첫 줄에는 테스트 케이스의 개수 $z$ ($1 \leq z \leq 100\,000$)가 주어진다. 이어서 각 테스트 케이스가 주어진다.

테스트 케이스의 첫 줄에는 정수 세 개 $n$, $q$, $H$ ($1 \leq n \leq 2\,000\,000$, $1 \leq q \leq 4\,000\,000$, $1 \leq H \leq 10^{12}$)가 주어진다. 각각 길의 길이, 날의 수, 게바이트의 초기 체력이다.

다음 $n$개 줄은 길의 초기 상태를 나타낸다. $i$번째 줄에는 대상의 종류를 나타내는 문자 (B, K, C 중 하나)와 정수 ($b_i$, $k_i$, $c_i$; $1 \leq b_i, k_i, c_i \leq 10^{12}$)가 주어지며, 뜻은 앞에서 설명한 것과 같다.

다음 $q$개 줄은 이후의 날들을 나타낸다. $i$번째 줄은 $i$일째에 길이 바뀌면 문자 Z로, 게바이트가 또 다른 여정을 상상하면 문자 D로 시작한다.

길을 바꾸는 경우 줄의 나머지에 바뀌는 대상의 번호 $x_i$ ($1 \leq x_i \leq n$)가 주어지고, 이어서 초기 상태와 같은 형식으로 새 대상을 나타내는 문자와 정수가 주어진다. 여정을 상상하는 경우 줄에는 출발 대상의 번호 $l_i$ ($1 \leq l_i \leq n$)가 주어진다.

모든 길의 길이의 합은 $2\,000\,000$을 넘지 않으며, 모든 날의 수의 합은 $4\,000\,000$을 넘지 않는다.

각 테스트 케이스마다 입력에 나온 순서대로 게바이트의 모든 질문에 대한 답을 출력한다. 각 질문에 대해서는 게바이트가 도달하고 살아남을 수 있는 가장 먼 대상의 번호 $r_i$ ($l_i \leq r_i \leq n$) 하나를 정수로 출력한다. $l_i$번째 대상에서 죽는다면 $-1$을 출력한다. $i$일째 질문에 대한 답에는 그 이전 날들에 이루어진 길의 모든 변경이 반영된다.

길은 다음과 같이 여섯 번 바뀐다.

• [C 10, B 5, K 5, B 6] (초기 상태)
• [C 10, B 5, K 6, B 6] (1일째)
• [C 11, B 5, K 6, B 6] (2일째)
• [C 11, B 5, C 1, B 6] (5일째)
• [C 11, B 5, B 20, B 6] (7일째)
• [C 31, B 5, B 20, B 6] (9일째)
• [C 31, B 5, B 20, K 6] (11일째)

나머지 여섯 날 동안 게바이트는 여러 여정을 상상한다.

3일째, 게바이트는 두 번째 대상에서 출발한다. 짐승을 죽이고 나면 체력이 5가 남는데, 다음 대상인 여관 K 6을 버티기에는 1이 모자란다. 따라서 그가 도달할 수 있는 가장 먼 대상은 두 번째이다.

4일째, 게바이트는 첫 번째 대상에서 출발한다. 마녀 덕분에 체력이 1 늘어나 세 번째 대상인 여관은 버티지만, 마지막 대상인 짐승에서 실패한다.

6일째, 게바이트는 세 번째 대상에서 출발한다. 이 대상은 이제 마녀 C 1이다. 체력은 그대로이므로 계속 나아가 길의 마지막 대상인 짐승을 죽인다.

8일째, 게바이트는 짐승 B 20에서 출발한다. 그는 이 짐승을 이길 수 없으므로 답은 -1이다.

10일째, 게바이트는 강력한 마녀 C 31에서 출발한다. 그 덕분에 처음 두 짐승을 이기지만, 마지막 짐승에서 실패한다.

마지막 날, 게바이트는 길 전체를 무사히 통과한다.