یک کلمه‌ ورودی $w$ و $p$ قانون تولید کلمه به‌صورت $x \longrightarrow yz$ داریم. اگر در $w$ از حرف $x$ استفاده شده باشد با استفاده از قانون $x \longrightarrow yz$ می‌توانیم حرف $x$ را حذف کنیم و به‌جای آن $yz$ بگذاریم. اگر در $w$ در بیش از یک‌جا $x$ آمده بود می‌توانیم یکی از این جا‌ها را به دلخواه انتخاب کنیم و قانون را روی آن اجرا کنیم. فرض کنید با کلمه‌ی $”g”$ شروع می‌کنیم و در تمام قوانین تولید کلمه فقط از حروف $”a…g”$ استفاده شده است. می‌خواهیم ببینیم آیا می‌توانیم با این قوانین کلمه‌ی $n$ حرفی $W$ را تولید کنیم.

در سطر اول ورودی $p$ آمده و در $p$ سطر بعد در هر سطر سه حرف از حروف $a…g$ آمده است. اگر این حروف به ترتیب برابر $x$ و $y$ و $z$ باشند، نشان‌دهنده‌ی قانون تولید $x \longrightarrow yz$ هستند. (بین این حروف فاصله است) در سطر $p+2$ ام ورودی ابتدا $n$ و سپس کلمه‌ی $n$ حرفی $W$‌ آمده است.( $1 \leq m \leq 7$)

اگر کلمه‌ی $W$ قابل تولید است، خروجی دارای $n-1$ سطر و هر سطر دارای ۲ عدد خواهد بود. در سطر $i$ ام شماره‌ی قانون تولید استفاده شده در مرحله $i$ ام و شماره‌ی حرفی که این کار روی آن انجام شده را بنویسید. در صورتی که این کار امکان پذیر نبود کلمه‌ی $Impossible$ را در فایل خروجی بنویسید.

• محدودیت زمان: ۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل