Just a sentence

Time Limit: 10 Seconds    Memory Limit: 32768 KB

می‌خواهیم با یک روش ساده یک برنامه تولید کنیم که جمله طبیعی ایجاد کند. البته مدل‌های واقعی این مساله خیلی علمی تر و واقعی‌تر هستند و ایده‌ای که در این مساله مطرح می‌شود خیلی ساده‌انگارانه است.

فرض کنید کلمه اول و آخر یک جمله را می‌دانید و می‌خواهید جمله ای ایجاد کنید که تعدادی کلمه بین این کلمه اول و آخر دارد. برای اینکار دو ابزار احتمالاتی نیاز دارید:

1. احتمال ظهور هر کلمه ( که به آن احتمال unigram می‌گویند)

2. احتمال ظهور هر کلمه به شرط کلمه قبلی ( که به آن احتمال bigram نیز می‌گویند)

با استفاده از ایندو می‌توانیم احتمال ظهور یک جمله ـ با فرض وابستگی هر کلمه به کلمه قبلی در جمله و استقلال آن از کلمات دیگرـ به صورت زیر تعریف نماییم:

با استفاده از این تعریف و ماتریس احتمالات (هردو‌ی الف و ب) و با گرفتن کلمه اول و آخر، محتمل ترین جمله (کلمات با ترتیب) را با احتمال تعریف شده در بالا بدست بیاورید. (توجه کنید که در ماتریس، با برابر نیست)

Input

ورودی شامل چند تست است، در خط اول ورودی تعداد تست‌ها T داده شده است. ()

در هرتست در خط اول N داده می‌شود که تعداد کل کلمات زبان است. ()

در خط بعد، ابتدا تمام کلمات (با space جدا شده) داده می‌شود و سپس در یک خط احتمال ظهور هر کلمه داده می‌شود. همچنین در یک خط اندیس کلمه اول و اندیس کلمه آخر (اندیس‌ها از ۱ شروع می‌شوند) جمله داده می‌شود. در N خط بعد، احتمال ظهور هر کلمه به شرط کلمه قبلی داده می‌شود.

Output

در خروجی به ازای هر تست کلمات جمله را به ترتیب در خروجی بنویسید

Sample Input

1
5
My name is Mohsen !
0.3 0.18 0.21 0.30 0.01
1 5
0.20 0.20 0.20 0.20 0.20
0.996 0.001 0.001 0.001 0.001
0.001 0.996 0.001 0.001 0.001
0.001 0.001 0.996 0.001 0.001
0.001 0.001 0.001 0.599 0.398

Sample Output

My name is Mohsen !

Submit