Little Cyan Fish는 문자열 이론을 매우 좋아합니다. 오늘 Little Cyan Fish는 당신을 초대하여 인간의 별명을 함께 연구하고자 합니다.

Little Cyan Fish의 우주에서 인간의 별명은 모두 영문 소문자(a부터 z까지)만 포함하는 문자열로 나타낼 수 있습니다. 예를 들어, qingyu, xiuga는 인간의 별명이지만, Abacde는 인간의 별명이 아닙니다.

인간으로서 당신의 현재 별명은 문자열 $s_0$입니다. Little Cyan Fish는 인간에게 $n$가지의 개명 기회를 제공하며, $i$번째 개명 기회는 양의 정수 $\ell_i$로 나타낼 수 있습니다. 이 개명 연산들은 원하는 순서대로 수행할 수 있지만, 각 개명 연산은 정확히 한 번씩 수행해야 합니다.

만약 $i$번째 종류의 개명 연산을 사용하기로 선택하면, 당신의 이름 $s$는 $s^\omega$의 첫 $\ell_i$개의 문자가 됩니다. 여기서 $s^\omega$는 문자열 $s$를 무한히 많이 이어 붙여 얻은 문자열을 뜻합니다. 예를 들어, 현재 이름이 $s = \text{ad}$일 때 $\ell = 5$인 개명 연산을 수행하면 당신의 이름은 $s' = \text{adada}$가 됩니다.

Little Cyan Fish는 인간의 별명이 사전순으로 가능한 한 커지기를 원합니다. 이제 Little Cyan Fish가 $s_0$와 $\ell_1, \ell_2, \dots, \ell_n$을 줍니다. $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$의 순서로 개명을 마친 후 최종적으로 얻어지는 문자열이 사전순으로 가장 크도록 하는 개명 순서 $p_1, p_2, \dots, p_n$($1 \le p_i \le n$, $p_i$는 길이가 $n$인 순열)을 찾으세요.

입력

여러 개의 테스트 케이스가 주어집니다. 입력의 첫 번째 줄에는 테스트 케이스의 개수를 나타내는 하나의 정수 $T$($1 \le T$)가 주어집니다.

각 테스트 케이스에 대해, 입력의 첫 번째 줄에는 당신의 초기 별명을 나타내는 문자열 $s_0$($1 \le |s_0| \le 10^5$, $s_0$는 영문 소문자만 포함함)가 주어집니다.

다음 줄에는 개명 기회의 개수를 나타내는 정수 $n$($1 \le n \le 10^5$)이 주어집니다.

다음 줄에는 각 개명 기회의 매개변수를 나타내는 $n$개의 정수 $\ell_1, \ell_2, \dots, \ell_n$($1 \le \ell_i \le 10^9$)이 주어집니다.

모든 테스트 케이스에서 $|s_0|$의 합은 $10^5$을 초과하지 않으며, 모든 테스트 케이스에서 $n$의 합도 $10^5$을 초과하지 않음이 보장됩니다.

출력

각 테스트 케이스에 대해, 당신의 개명 순서를 나타내는 $n$개의 정수 $p_1, p_2, \dots, p_n$($1 \le p_i \le n$, $p_i$는 길이가 $n$인 순열)을 한 줄에 출력합니다.

예제

예제 입력 1

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

예제 출력 1

2 1
1 2
3 6 2 1 4 5