Số yêu thích của Jayden là chuỗi \(x\) gồm \(m\) chữ số. Ziv đưa cho cậu \(n\) chuỗi \(m\) chữ số khác, ký hiệu \(v_1,v_2,\ldots,v_n\). Mọi chữ số đều thuộc \([0,k-1]\). Ký hiệu \(v_i[j]\) là chữ số thứ \(j\) từ trái sang của \(v_i\).

Một thao tác trên \(v_i\) được thực hiện như sau:

1. Chọn \(1\le l\le r\le m\).
2. Với mọi \(l\le j\le r\), thay \(v_i[j]\) bởi \((v_i[j]+a_j)\bmod k\).

Chi phí của thao tác là \(c_l+c_r\) (nếu \(l=r\) thì chi phí là \(2c_l\)).

Với từng \(v_i\) một cách độc lập, hãy tìm tổng chi phí nhỏ nhất để biến \(v_i\) thành \(x\) bằng một số bất kỳ thao tác. Nếu không thể, in \(-1\).

Dữ liệu vào

• Dòng đầu chứa \(n,m,k\).
• Dòng thứ hai chứa \(a_1,a_2,\ldots,a_m\).
• Dòng thứ ba chứa \(c_1,c_2,\ldots,c_m\).
• Dòng thứ tư chứa chuỗi \(x\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa chuỗi \(v_i\).

Các chuỗi có thể có chữ số 0 ở đầu, vì vậy cần đọc chúng dưới dạng chuỗi.

Dữ liệu ra

In \(n\) dòng. Dòng thứ \(i\) là chi phí nhỏ nhất để biến \(v_i\) thành \(x\), hoặc \(-1\) nếu không thể.

Giới hạn

Chấm điểm

Ví dụ

6 3 8
1 2 3
3 1 4
676
356
431
676
767
133
715

16
42
0
-1
25
37

Với \(v_1=356\), có thể thực hiện lần lượt các thao tác \([1,2]\), \([1,1]\), \([1,1]\) để được \(356\to476\to576\to676\), tổng chi phí \(4+6+6=16\). Chuỗi \(v_3\) đã bằng \(x\). Không có cách biến \(v_4=767\) thành \(676\).

3 4 2
1 1 1 1
1 1 1 1
1001
1110
1100
0110

2
4
2

1 1 10
1
67
6
7

1206

1 2 10
1 1
1 1000000000
24
83

1000000007