Little Cyan Fish rất thích lý thuyết dây (lý thuyết xâu). Hôm nay, Little Cyan Fish mời bạn cùng cậu nghiên cứu về biệt danh của con người.

Trong vũ trụ của Little Cyan Fish, biệt danh của con người đều có thể được biểu diễn dưới dạng một xâu chỉ chứa các chữ cái Latinh thường (a đến z). Ví dụ, qingyu, xiuga là biệt danh của con người, nhưng Abacde không phải là biệt danh của con người.

Là một con người, biệt danh hiện tại của bạn là xâu $s_0$. Little Cyan Fish cung cấp cho con người $n$ cơ hội đổi tên, cơ hội đổi tên thứ $i$ có thể được biểu diễn bằng một số nguyên dương $\ell_i$. Bạn có thể thực hiện các thao tác đổi tên này theo bất kỳ thứ tự nào, nhưng mỗi thao tác đổi tên phải được thực hiện đúng một lần.

Nếu bạn chọn sử dụng thao tác đổi tên loại thứ $i$, thì tên $s$ của bạn sẽ trở thành $\ell_i$ ký tự đầu tiên của $s^\omega$, trong đó $s^\omega$ ký hiệu xâu thu được bằng cách lặp lại xâu $s$ vô hạn lần. Ví dụ, nếu tên hiện tại của bạn là $s = \text{ad}$, thì sau khi thực hiện thao tác đổi tên với $\ell = 5$, tên của bạn sẽ trở thành $s' = \text{adada}$.

Little Cyan Fish muốn biệt danh của con người trở nên lớn nhất có thể theo thứ tự từ điển. Bây giờ, Little Cyan Fish đưa ra $s_0$ và $\ell_1, \ell_2, \dots, \ell_n$. Bạn cần tìm một thứ tự đổi tên $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ là một hoán vị có độ dài $n$), sao cho sau khi đổi tên theo thứ tự $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$, xâu cuối cùng thu được có thứ tự từ điển lớn nhất có thể.

Dữ liệu vào

Có nhiều bộ test. 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$), cho biết số lượng bộ test.

Với mỗi bộ test, dòng đầu tiên chứa một xâu $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ chỉ chứa các chữ cái Latinh thường), cho biết biệt danh ban đầu của bạn.

Dòng tiếp theo chứa một số nguyên $n$ ($1 \le n \le 10^5$), cho biết số lượng cơ hội đổi tên.

Dòng tiếp theo chứa $n$ số nguyên $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$), cho biết tham số của mỗi cơ hội đổi tên.

Đảm bảo rằng tổng của $|s_0|$ trên tất cả các bộ test không vượt quá $10^5$, và tổng của $n$ trên tất cả các bộ test không vượt quá $10^5$.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng duy nhất chứa $n$ số nguyên $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ là một hoán vị có độ dài $n$), cho biết thứ tự đổi tên của bạn.

Ví dụ

Dữ liệu vào 1

3
qingyu
2
7 3
abacde
2
8 11
abcabadefdghiajkd
6
11 4 5 14 1919 810

Dữ liệu ra 1

2 1
1 2
3 6 2 1 4 5