Cho một xâu ~S~ gồm các chữ cái Latinh viết hoa, một số nguyên dương ~C~ và một dãy gồm ~|S|~ phần tử ~A_1, A_2, \cdots, A_{|S|}~.

Xuất phát tại một vị trí ~1 \le i \le |S|~, hãy tìm chi phí nhỏ nhất để di chuyển và biến đổi xâu ~S~ thành palindrome.

Biết rằng từ vị trí ~i~ di chuyển tới ~i - 1~ hoặc ~i + 1~ sẽ tốn ~C~ chi phí. Tại một vị trí ~j~ bất kì, ta được phép biến đổi ~S_j~ thành bất cứ kí tự nào với chi phí là ~A_j~.

In ra chi phí nhỏ nhất với mọi vị trí.

Input

Dữ liệu vào từ file văn bản palin.inp:

Dòng đầu tiên chứa số nguyên ~T~ (~1 \le T \le 1000~) — Số test. Với mỗi test:

• Dòng đầu tiên của test chứa xâu ~S~ (~1 \le |S| \le 10^6~) — Xâu ~S~ chỉ gồm các chữ cái Latin viết hoa.

• Dòng tiếp theo chứa số nguyên dương ~C~ (~1 \le C \le 10^9~) — Chi phí một bước di chuyển.

• Dòng cuối cùng chứa ~|S|~ số nguyên ~A_1, A_2, \cdots, A_n~ (~1 \le A_i \le 10^9~) — Chi phí một phép biến đổi của mỗi vị trí.

Dữ liệu đảm bảo tổng ~|S|~ của tất cả các test không vượt quá ~10^6~.

Output

Dữ liệu in ra file văn bản palin.out:

Với mỗi test, trên một dòng in ra ~|S|~ số nguyên là chi phí nhỏ nhất để biến đổi xâu ~S~ thành palindrome với mọi vị trí.

Scoring

Sample Input 1

2
ABCDE
1
7 1 4 5 1
ABCDA
1
7 1 4 5 1

Sample Output 1

6 5 6 6 5
2 1 2 3 4

Notes

Ở ví dụ thứ nhất, bắt đầu ở vị trí ~1~, một trong những cách tối ưu là di chuyển sang vị trí ~2~ tốn ~1~, đổi "B" thành "D" tốn ~1~, sau đó di chuyển đến vị trí ~5~ tốn ~3~ và đổi "E" thành "A" tốn ~1~. Tổng cộng là ~6~.