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$ יהפוך ל-$\ell_i$ התווים הראשונים של $s^\omega$, כאשר $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$. עליך למצוא סדר שינוי שם כלשהו $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i$ הוא תמורה באורך $n$), כך שלאחר שינוי השם בסדר $\ell_{p_1}, \ell_{p_2}, \dots, \ell_{p_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