길이가 $n$인 정수 배열 $a$가 있다. 처음에 $a$의 모든 원소는 0이다. 케빈은 배열에 대해 여러 연산을 수행할 수 있다. 각 연산은 다음 두 가지 유형 중 하나이다.

• 접두사 더하기(Prefix addition) — 케빈이 먼저 인덱스 $x$ ($1 \le x \le n$)를 선택한 다음, 각 $1 \le j \le x$에 대하여 $a_j$를 1만큼 증가시킨다.
• 접미사 더하기(Suffix addition) — 케빈이 먼저 인덱스 $x$ ($1 \le x \le n$)를 선택한 다음, 각 $x \le j \le n$에 대하여 $a_j$를 1만큼 증가시킨다.

KDOI라는 나라에서는 정수 $v$가 균형 잡혀 있다고 생각한다. 그래서 아이리스는 케빈에게 $n$개의 정수로 이루어진 배열 $c$를 주고, 배열 $a$의 아름다움(beauty)을 다음과 같이 정의한다.

• 처음에 $b = 0$으로 설정한다.
• 각 $1 \le i \le n$에 대하여, 만약 $a_i = v$이면 $b$에 $c_i$를 더한다.
• 배열 $a$의 아름다움은 $b$의 최종 값이다.

케빈은 모든 연산이 끝난 후 $a$의 아름다움을 최대화하고 싶어 한다. 하지만 그는 졸린 상태에서 이미 $m$번의 연산을 수행했다. 이제 그는 임의의 횟수(0번 포함)만큼 새로운 연산을 수행할 수 있다.

케빈이 새로운 연산을 최적으로 수행했을 때 얻을 수 있는 최대 아름다움을 찾도록 도와주어야 한다. 하지만 단순히 운에 맡기는 것이 아님을 보장하기 위해, 케빈은 정수 $V$를 주며, 당신은 모든 $1 \le v \le V$에 대하여 문제를 해결해야 한다.

입력

각 테스트 케이스는 여러 개의 테스트 케이스를 포함한다. 입력의 첫 번째 줄에는 테스트 케이스의 수 $t$ ($1 \le t \le 1000$)가 주어진다. 각 테스트 케이스에 대한 설명이 이어진다.

각 테스트 케이스의 첫 번째 줄에는 세 정수 $n, m, V$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le V \le 2000$)가 주어진다. 이는 배열 $a$의 길이, 초기 연산의 횟수, 그리고 케빈이 준 정수를 의미한다.

두 번째 줄에는 $n$개의 정수 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$)이 주어진다. 이는 배열 $c$의 원소들이다.

그다음 $m$개의 줄이 이어지며, $i$번째 줄에는 문자 $op$와 정수 $x$ ($op = \text{L}$ 또는 $\text{R}$, $1 \le x \le n$)가 주어진다. 이는 $i$번째 연산의 유형과 선택된 인덱스를 의미한다.

• $op = \text{L}$이면, 이 연산은 인덱스 $x$에 대한 접두사 더하기이다.
• $op = \text{R}$이면, 이 연산은 인덱스 $x$에 대한 접미사 더하기이다.

다음이 보장된다.

• 모든 테스트 케이스에 대한 $n$의 합은 $2 \cdot 10^5$를 넘지 않는다.
• 모든 테스트 케이스에 대한 $m$의 합은 $2 \cdot 10^5$를 넘지 않는다.
• 모든 테스트 케이스에 대한 $V^2$의 합은 $4 \cdot 10^6$을 넘지 않는다.

출력

각 테스트 케이스마다, $V$개의 정수를 한 줄에 출력한다. $i$번째 정수는 $v = i$일 때 케빈이 새로운 연산을 수행한 후 얻을 수 있는 최대 아름다움을 나타낸다.

예제

입력 1

5
3 3 2
1 2 4
L 3
R 3
L 1
3 3 2
5 1 4
L 3
R 3
L 1
5 4 5
1 1 1 1 1
L 3
R 2
L 5
L 4
10 12 9
10 9 8 7 6 5 4 3 2 1
L 2
L 4
R 4
R 4
L 6
R 8
L 3
L 2
R 1
R 10
L 8
L 1
1 1 4
1000000000
L 1

출력 1

2 6
1 9
0 1 3 5 5
0 0 0 6 25 32 35 44 51
1000000000 1000000000 1000000000 1000000000

참고

첫 번째 테스트 케이스에서, 초기 연산에 따라 배열 $a$는 다음과 같이 변한다: $[0, 0, 0] \xrightarrow{\text{L } 3} [1, 1, 1] \xrightarrow{\text{R } 3} [1, 1, 2] \xrightarrow{\text{L } 1} [2, 1, 2]$.

• $v = 1$일 때, 새로운 연산을 수행하지 않는 것이 최적이며, 아름다움은 $b = c_2 = 2$이다.
• $v = 2$일 때, 인덱스 2에 접두사 더하기 연산을 수행하는 것이 최적이다. 그 후 $a$는 $[3, 2, 2]$가 되고, 아름다움은 $b = c_2 + c_3 = 6$이 된다.

두 번째 테스트 케이스에서는 $v = 1$과 $v = 2$ 모두 새로운 연산을 수행하지 않는 것이 최적이다.