يحب 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 أن تصبح ألقاب البشر أكبر ما يمكن من الناحية المعجمية (lexicographically). الآن، يعطيك 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