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