+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- > باب جدیداً با موتور جستجوی هوشمند خرید *ترب* آشنا شده و در حال نوشتن نام کالای مورد نظرش در بخش جستجوی سایت است. در موتور جستجوی هوشمند خرید *ترب* $n$ نوع کالا وجود دارد که اسم هر‌ کدام از تعدادی کلمه تشکیل شده است. *ترب* پیش‌بینی کرده است که احتمال آن که کسی کالای شماره‌ی $i$ را بخرد، برابر $\frac{p_i}{1 \ 000 \ 000}$ است. موتور جستجوی هوشمند خرید *ترب* یک سیستم تکمیل خودکار دارد که این‌گونه عمل می‌کند که بین **کالاهایی که عبارت وارد شده توسط کاربر پیشوند نام آن کالا است**، کالایی که بیشترین احتمال جستجو شدن (یا همان $\frac{p_i}{1 \ 000 \ 000}$ ) را دارد را انتخاب می‌کند ( اگر چند کالا با بیشترین احتمال خرید وجود داشت، کالایی که از نظر ترتیب الفبایی کوچک‌ترین است انتخاب می‌شود). تضمین می‌شود که حتما سیستم تکمیل خودکار می‌تواند کالایی را برای تکمیل شناسایی کند. نام $a$ ($a_1,a_2,..,a_x$) پیشوند نام $b$ ($b_1,b_2,...,b_y$) است اگر $x \le y$ و $a_1=b_1,a_2=b_2,...,a_x=b_x$ هر‌دو صادق باشد و $a_i$ و $b_i$ها هر‌کدام یک کلمه باشند. در ترتیب الفبایی کلمه $a$ کوچک‌تر از کلمه $b$ است اگر یکی از دو شرط زیر برقرار باشد: 1. کلمه $a$ پیشوند $b$ باشد. 2. اندیس $i$-ای وجود داشته باشد که $ a_1=b_1,a_2=b_2,...,a_{i-1}=b_{i-1}$ و $a_i$ در الفبا قبل از $b_i$ بیاید. الفبا در اینجا همان کد [اسکی](https://fa.wikipedia.org/wiki/%D8%A7%D8%B3%DA%A9%DB%8C_%28%D8%A7%D8%B3%D8%AA%D8%A7%D9%86%D8%AF%D8%A7%D8%B1%D8%AF%29) است. برای مثال کلمه `abc` کوچک‌تر از `abcde` است و کلمه `abcd` کوچک‌تر از `abgd` است. مقایسه‌ی نام‌ها همانند کلمات است ولی در $a_i$ ها و $b_i$ ها به جای حروف کلمات می‌آیند. *باب* در *ترب* $m$ بار جستجو کرده‌است. با داشتن نام و احتمال‌های جستجو‌ی هر کالا و جستجو‌ی های *باب*، نام کالایی که سیستم تکمیل خودکار *ترب* برای هر جستجو بدست می‌آورد را خروجی‌دهید. تضمین می‌شود مجموع تمام احتمال‌ها برابر $1$ می‌شود. البته این سیستم خیلی ساده‌تر از سیستمی است که در *ترب* وجود دارد، و برای درک بهترِ *باب* تا حد زیادی ساده‌سازی شده‌است. # ورودی در خط اول ورودی عدد $n$ داده‌ می‌شود که تعداد نوع کالاهای موجود در موتور جستجوی هوشمند *ترب* است. سپس در همان خط عدد $m$ داده می‌شود که تعداد جستجو‌های *باب* است. در هر یک از $n$ خط بعد ابتدا عدد $k$ داده‌ می‌شود که تعداد کلمات نام آن کالا است. سپس در همان خط عدد $p_i$ داده می‌شود که احتمال آن است کسی بخواهد آن کالا را بخرد. سپس در همان خط $k$ رشته داده می‌شود که کلمات نام آن کالا است. طول هر یک از کلمات حداکثر $10$ است و از ارقام و حروف انگلیسی تشکیل شده‌اند. در هر یک از $m$ خط بعد ابتدا عدد $k$ که تعداد کلمات نوشته‌شده توسط باب به ازای هر جستجو است و سپس در همان خط $k$ رشته که کلماتی است که باب به ازای آن جستجو نوشته‌است داده می‌شود. $$1\le n,m \le 1\ 000$$ $$0\le p_i \le 1\ 000\ 000$$ $$1\le k\le 5$$ $$\sum_{i=1}^{n} p_i = 1 \ 000 \ 000$$ # خروجی در هر یک از $m$ خط خروجی به ازای هر یک از جستجو‌های *باب* نام کالایی که سیستم تکمیل خودکار موتور جستجوی هوشمند *ترب* تشخیص می‌دهد را خروجی دهید. # مثال ## ورودی نمونه ``` 4 5 4 100000 Smartphone Samsung Galaxy s8 3 200000 Smartphone iPhone 8 4 300000 Smartphone Samsung Galaxy s8plus 4 400000 Smartphone iPhone X gray256gb 1 Smartphone 3 Smartphone iPhone X 4 Smartphone iPhone X gray256gb 2 Smartphone iPhone 4 Smartphone Samsung Galaxy s8plus ``` ## خروجی نمونه ``` Smartphone iPhone X gray256gb Smartphone iPhone X gray256gb Smartphone iPhone X gray256gb Smartphone iPhone X gray256gb Smartphone Samsung Galaxy s8plus ``` توضیح: برای جستجوی اول کالا‌های نوع های ۱و۲و۳و۴ ممکن است مورد خواست *باب* باشد و در بین آن ها کالای نوع ۴ از همه احتمال بیشتری را دارد. برای دومین جستجو فقط کالای نوع ۴ امکان‌پذیر است. برای سومین جستجو نیز فقط کالای نوع ۴ امکان‌پذیر است. برای چهارمین جستجو کالاها‌ی نوع ۲و۴ امکان‌پذیر هستند و در بین آن‌ها کالای‌ شماره‌ی ۴ احتمال بیشتری دارد. برای پنجمین جستجو فقط کالای نوع ۳ امکان‌پذیر است.

حل سؤال در بانک سؤالات