Little Cyan Fish likes string theory very much. Today, Little Cyan Fish invites you to study human nicknames with him.

In Little Cyan Fish's universe, human nicknames can all be represented as a string containing only lowercase Latin letters (a to z). For example, qingyu, xiuga are human nicknames, but Abacde is not a human nickname.

As a human, your current nickname is the string $s_0$. Little Cyan Fish offers humans $n$ kinds of renaming opportunities, the $i$-th renaming opportunity can be represented by a positive integer $\ell_i$. You can execute these renaming operations in any order, but each renaming operation must be executed exactly once.

If you choose to use the $i$-th type of renaming operation, then your name $s$ will become the first $\ell_i$ characters of $s^\omega$, where $s^\omega$ denotes the string obtained by copying the string $s$ infinitely many times. For example, if your current name is $s = \text{ad}$, then after executing the renaming operation with $\ell = 5$, your name will become $s' = \text{adada}$.

Little Cyan Fish wants human nicknames to become as lexicographically large as possible. Now, Little Cyan Fish gives $s_0$ and $\ell_1, \ell_2, \dots, \ell_n$. You need to find some renaming order $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ is a permutation of length $n$), such that after renaming in the order of $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$, the final string obtained has the largest possible lexicographical order.

Input

There are multiple test cases. The first line of the input contains a single integer $T$ ($1 \le T$), indicating the number of test cases.

For each test case, the first line of the input contains a string $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ only contains lowercase Latin letters), indicating your initial nickname.

The next line contains an integer $n$ ($1 \le n \le 10^5$), indicating the number of renaming opportunities.

The next line contains $n$ integers $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$), indicating the parameters of each renaming opportunity.

It is guaranteed that the sum of $|s_0|$ over all test cases does not exceed $10^5$, and the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single line containing $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ is a permutation of length $n$), indicating your renaming order.

Example

Input 1

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

Output 1

2 1
1 2
3 6 2 1 4 5