سوال ۳

آقای مهندس و خانم دکتر خیلی بچه دوست دارند اما برای اسم‌گذاری فرزندانشان خیلی وقت نمی‌گذارند. آن‌ها اسم فرزند $i$ام شان را کوتا‌هترین رشته شامل $k$ حرف اول انگلیسی انتخاب می‌کنند که هیچ ناسزایی زیرر‌شته‌ی این اسم نباشد و هم‌چنین با اسم بچه‌های بزرگتر مساوی نباشد. (دقت کنید که نام یک فرزند نمی‌تواند یک رشته‌ی خالی باشد) در صورتی که چندین اسم با کوتاهترین طول وجود داشته باشد، آن‌ها اسمی را که از لحاظ الفبایی از بقیه کوچک‌تر است انتخاب می‌کنند. برنامه‌ای بنویسید که به پرسمان‌های به شکل «بزرگترین پیشوند مشترک اسم $i$امین و $j$امین فرزند چیست؟» جواب بدهد.

به طوری دقیق‌تر، اگر اسم فرزند $n$ام را $S = S_1S_2. . S_l$ در نظر بگیریم و $T$ یک ناسزا باشد، هیچ $i$ای نباید وجود داشته باشد به طوری که $S_iS_{i + 1}. . S_{i + ∣T∣ − 1} = T$ برقرار باشد.

• سطر اول ورودی شامل چهار عدد طبیعی $m$، تعداد ناسزا‌ها، $k$، تعداد حروف انگلیسی مجاز، و $n$، تعداد فرزندان و $q$، تعداد پرسمان‌ها، آمده است.
• در هر یک از $m$ سطر بعدی، یک رشته‌ تشکیل شده از $k$ حرف کوچک انگلیسی آمده‌ است که مشخص‌ کننده‌ی یک ناسزا است.
• در هر یک از $q$ سطر بعدی، یک پرسمان آمده است که یکی از دو فرم زیر است:
• $x\ y$ @ : بزرگترین پیشوند مشترک اسم $x$امین و $y$امین فرزند را چاپ کنید.
• $x\ y$ # : طول بزرگترین پیشوند مشترک اسم $x$امین و $y$امین فرزند را چاپ کنید.
• تضمین می‌شود که حتم می‌توان برای $n$ فرزند اسم‌گذاری کرد.
• حداکثر $۴۰$ پرسمان به فرم @ هستند.
• مجموع طول ناسزا‌ها حداکثر $۲۰۰$ است.
• $1 \leq n, q \leq 10^5$
• $1 \leq k \leq 26$
• $1 \leq m \leq 200$
• $1 \leq x, y \leq n$

در $q$ سطر خروجی، در هر سطر پاسخ یک پرسمان را چاپ کنید. اگر فرم پرسمان @ باشد و رشته‌ای که باید چاپ شود تهی باشد، عبارت ‍‍I'm a blackboard را چاپ کنید.

• زیرمسئله اول (۱۰ نمره): $n, m, q \leq 50$
• زیرمسئله دوم (۲۰ نمره): $n, q \leq 1000$ و تمامی پرسمان‌ها به صورت $x \ x$ # هستند.
• زیرمسئله سوم (۲۰ نمره): $n, q \leq 1000$ و تمامی پرسمان‌ها به صورت $x \ x$ # یا $x \ x$ @ هستند.
• زیرمسئله چهارم (۵۰ نمره): بدون محدودیت اضافی

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

• سوال قبل