Có một mảng $a$ gồm $n$ số nguyên. Ban đầu, tất cả các phần tử của $a$ đều bằng 0. Kevin có thể thực hiện một số thao tác trên mảng. Mỗi thao tác thuộc một trong hai loại sau:

• Cộng tiền tố — Kevin chọn một chỉ số $x$ ($1 \le x \le n$), sau đó với mỗi $1 \le j \le x$, tăng $a_j$ lên 1.
• Cộng hậu tố — Kevin chọn một chỉ số $x$ ($1 \le x \le n$), sau đó với mỗi $x \le j \le n$, tăng $a_j$ lên 1.

Tại đất nước KDOI, người ta cho rằng số nguyên $v$ là cân bằng. Do đó, Iris đưa cho Kevin một mảng $c$ gồm $n$ số nguyên và định nghĩa vẻ đẹp của mảng $a$ như sau:

• Ban đầu, đặt $b = 0$.
• Với mỗi $1 \le i \le n$, nếu $a_i = v$, cộng $c_i$ vào $b$.
• Vẻ đẹp của $a$ là giá trị cuối cùng của $b$.

Kevin muốn tối đa hóa vẻ đẹp của $a$ sau tất cả các thao tác. Tuy nhiên, anh ấy đã thực hiện $m$ thao tác khi đang buồn ngủ. Bây giờ, anh ấy có thể thực hiện một số lượng tùy ý (có thể bằng không) các thao tác mới.

Bạn cần giúp Kevin tìm vẻ đẹp tối đa có thể đạt được nếu anh ấy thực hiện các thao tác mới một cách tối ưu. Tuy nhiên, để đảm bảo bạn không chỉ đoán mò, Kevin đưa cho bạn một số nguyên $V$, và bạn cần giải bài toán cho mỗi $1 \le v \le V$.

Dữ liệu vào

Mỗi bộ dữ liệu chứa nhiều trường hợp kiểm thử. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $t$ ($1 \le t \le 1000$) — số lượng trường hợp kiểm thử. Tiếp theo là mô tả các trường hợp kiểm thử.

Dòng đầu tiên của mỗi trường hợp kiểm thử chứa ba số nguyên $n, m$ và $V$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le V \le 2000$) — độ dài của mảng $a$, số lượng thao tác ban đầu, và số mà Kevin đưa cho bạn.

Dòng thứ hai chứa $n$ số nguyên $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — các phần tử trong mảng $c$.

Sau đó là $m$ dòng, dòng thứ $i$ chứa một ký tự $op$ và một số nguyên $x$ ($op = \text{L}$ hoặc $\text{R}$, $1 \le x \le n$) — loại của thao tác thứ $i$ và chỉ số được chọn.

• Nếu $op = \text{L}$, đây là thao tác cộng tiền tố tại chỉ số $x$.
• Nếu $op = \text{R}$, đây là thao tác cộng hậu tố tại chỉ số $x$.

Đảm bảo rằng:

• Tổng của $n$ trên tất cả các trường hợp kiểm thử không vượt quá $2 \cdot 10^5$.
• Tổng của $m$ trên tất cả các trường hợp kiểm thử không vượt quá $2 \cdot 10^5$.
• Tổng của $V^2$ trên tất cả các trường hợp kiểm thử không vượt quá $4 \cdot 10^6$.

Dữ liệu ra

Với mỗi trường hợp kiểm thử, in ra $V$ số nguyên trên một dòng, số nguyên thứ $i$ biểu thị vẻ đẹp tối đa có thể đạt được sau khi Kevin thực hiện một số thao tác mới khi $v = i$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

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

Ghi chú

Trong trường hợp kiểm thử đầu tiên, mảng $a$ thay đổi như sau qua các thao tác ban đầu: $[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ới $v = 1$, tối ưu nhất là không thực hiện thêm thao tác mới nào, và vẻ đẹp là $b = c_2 = 2$.
• Với $v = 2$, tối ưu nhất là thực hiện một thao tác cộng tiền tố tại chỉ số 2. Sau đó, $a$ trở thành $[3, 2, 2]$, và vẻ đẹp là $b = c_2 + c_3 = 6$.

Trong trường hợp kiểm thử thứ hai, với cả $v = 1$ và $v = 2$, tối ưu nhất là không thực hiện thêm thao tác mới nào.