지상 방어

당신은 라인토피아의 주민이다. 라인토피아의 주요 도시 $n$개는 동서로 뻗은 직선 위에 같은 간격으로 놓여 있다. 도시에는 서쪽부터 차례로 $1$부터 $n$까지 번호가 붙어 있어서 $1$번이 가장 서쪽, $n$번이 가장 동쪽 도시다. 라인토피아는 살기 좋은 곳이었지만 이웃 나라 트라페즈의 군대가 쳐들어왔다. 라인토피아의 시민 보호 계획에 따라 당신은 트라페즈군의 이동 정보를 처리하는 일을 맡았다. 어느 도시가 가장 큰 피해를 입었는지 알아내서 지원군을 보낼 곳을 정하기 위해서다.

라인토피아 정보부가 알아낸 트라페즈군의 공격 방식은 다음과 같다. 트라페즈군은 거대한 수송기로 라인토피아의 도시에 병력을 투하한다. 각 수송기는 어떤 도시 $i$에서 출발하며 그 도시에 병사 $s$명을 떨어뜨린다. 그다음 수송기는 동쪽이나 서쪽 중 한 방향으로 날아간다. 다른 도시 위를 지날 때마다 직전에 지난 도시보다 $a$명 더 많은 병사를 떨어뜨린다. 투하를 $d$번 하고 나면 수송기는 보급을 받으러 트라페즈로 돌아간다.

당신은 라인토피아 상공을 지나는 트라페즈 수송기의 제원을 알려 주는 정보를 차례로 받는다. 이와 함께 특정 도시에 지금까지 투하된 트라페즈 병사가 몇 명인지 묻는 질의에 답해야 한다.

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 10$)가 주어진다. 각 테스트 케이스의 첫째 줄에는 갱신과 질의의 총개수 $m$ ($1 \le m \le 10\,000$)과 라인토피아의 도시 수 $n$ ($1 \le n \le 500\,000$)이 주어진다.

다음 $m$개의 줄에는 갱신 또는 질의가 주어진다. 갱신 줄은 대문자 U로 시작하고, 이어서 방향을 나타내는 대문자 E(동쪽) 또는 W(서쪽)가 온다. 그 뒤에 정수 네 개 $i$ ($1 \le i \le n$), $s$ ($1 \le s \le 10\,000$), $a$ ($0 \le a \le 10\,000$), $d$ ($1 \le d \le n$)가 주어진다. 이 정수들은 차례로 출발 도시, 처음 투하하는 병사 수, 도시마다 늘어나는 병사 수, 투하 횟수를 뜻한다. 수송기가 $d$번 투하하는 동안 $1$번 도시보다 서쪽이나 $n$번 도시보다 동쪽으로 날아가는 일은 없다.

질의 줄은 대문자 Q로 시작하고, 이어서 질의하는 도시를 나타내는 정수 $i$ ($1 \le i \le n$)가 하나 주어진다.

입력의 각 질의마다 그 시점까지 해당 도시에 투하된 트라페즈 병사의 수를 한 줄에 하나씩 출력한다.

예제에서는 수송기 두 대가 라인토피아 상공을 지난다. 첫 번째 수송기는 $1$번 도시에서 출발해 동쪽으로 날아가며 $1$번 도시에 $5$명, $2$번 도시에 $7$명, $3$번 도시에 $9$명을 떨어뜨린다. 두 번째 수송기는 $3$번 도시에서 출발해 서쪽으로 날아가며 $3$번 도시에 $10$명, $2$번 도시에 $20$명을 떨어뜨린다.