Little Cyan Fish sangat menyukai teori string. Hari ini, Little Cyan Fish mengundang Anda untuk mempelajari nama panggilan manusia bersamanya.

Di alam semesta Little Cyan Fish, nama panggilan manusia semuanya dapat direpresentasikan sebagai sebuah string yang hanya berisi huruf-huruf Latin kecil (a hingga z). Sebagai contoh, qingyu, xiuga adalah nama panggilan manusia, tetapi Abacde bukan nama panggilan manusia.

Sebagai seorang manusia, nama panggilan Anda saat ini adalah string $s_0$. Little Cyan Fish menawarkan $n$ jenis kesempatan penggantian nama kepada manusia, di mana kesempatan penggantian nama ke-$i$ dapat direpresentasikan dengan sebuah bilangan bulat positif $\ell_i$. Anda dapat menjalankan operasi-operasi penggantian nama ini dalam urutan apa pun, tetapi setiap operasi penggantian nama harus dijalankan tepat satu kali.

Jika Anda memilih untuk menggunakan operasi penggantian nama jenis ke-$i$, maka nama Anda $s$ akan menjadi $\ell_i$ karakter pertama dari $s^\omega$, di mana $s^\omega$ menyatakan string yang diperoleh dengan menyalin string $s$ sebanyak tak hingga kali. Sebagai contoh, jika nama Anda saat ini adalah $s = \text{ad}$, maka setelah menjalankan operasi penggantian nama dengan $\ell = 5$, nama Anda akan menjadi $s' = \text{adada}$.

Little Cyan Fish ingin nama panggilan manusia menjadi sebesar mungkin secara leksikografis. Sekarang, Little Cyan Fish memberikan $s_0$ dan $\ell_1, \ell_2, \dots, \ell_n$. Anda perlu mencari suatu urutan penggantian nama $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ adalah permutasi dengan panjang $n$), sedemikian sehingga setelah melakukan penggantian nama dalam urutan $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_n}$, string akhir yang diperoleh memiliki urutan leksikografis terbesar yang mungkin.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T$), yang menyatakan banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama dari masukan berisi sebuah string $s_0$ ($1 \le |s_0| \le 10^5$, $s_0$ hanya berisi huruf-huruf Latin kecil), yang menyatakan nama panggilan awal Anda.

Baris berikutnya berisi sebuah bilangan bulat $n$ ($1 \le n \le 10^5$), yang menyatakan banyaknya kesempatan penggantian nama.

Baris berikutnya berisi $n$ bilangan bulat $\ell_1, \ell_2, \dots, \ell_n$ ($1 \le \ell_i \le 10^9$), yang menyatakan parameter dari setiap kesempatan penggantian nama.

Dijamin bahwa jumlah dari $|s_0|$ di semua kasus uji tidak melebihi $10^5$, dan jumlah dari $n$ di semua kasus uji tidak melebihi $10^5$.

Keluaran

Untuk setiap kasus uji, cetak satu baris yang berisi $n$ bilangan bulat $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ adalah permutasi dengan panjang $n$), yang menyatakan urutan penggantian nama Anda.

Contoh

Masukan 1

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

Keluaran 1

2 1
1 2
3 6 2 1 4 5