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

---

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

به طور دقیق‌تر، اگر اسم فرزند $n$-ام را $ S = S_1 S_2 \cdots S_l $ در نظر بگیریم و T یک ناسزا باشد، هیچ i و jای نباید وجود داشته باشد که $ S_i S_i+1 \cdots S_j = T $ برقرار باشد.

ورودی

سطر اول ورودی شامل چهار عدد طبیعی m، تعداد ناسزا‌ها، k، تعداد حروف انگلیسی مجاز، n، تعداد فرزندان و q، تعداد پرسمان‌ها آمده است.

در هر یک از m سطر بعدی، یک رشته‌ تشکیل شده از k حرف کوچک انگلیسی آمده‌ است که مشخص‌ کننده‌ی یک ناسزا است.

در هر یک از $q$ سطر بعدی، یک پرسمان آمده است که به یکی از دو شکل زیر است:

• عبارت x y @ : بزرگترین پیشوند مشترک اسم $i$-امین و $j$-امین فرزند را چاپ کنید.

• عبارت x y # : طول بزرگترین پیشوند مشترک اسم $i$-امین و $j$-امین فرزند را چاپ کنید.

تضمین می‌شود که حتمن می‌توان برای $n$ فرزند اسم‌گذاری کرد. حداکثر ۴۰ پرسمان به فرم @ هستند. مجموع طول ناسزا‌ها حداکثر ۲۰۰ است.

$$1\le n,q\le 100\ 000$$

$$1\le k\le 26$$

$$1\le m\le 200$$

$$1\le x,y \le n$$

خروجی

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

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۱۰	$ n,m,q \le 50 $
۲	۲۰	$ m , q \le 1\ 000$ و همه پرسمان‌ها به صورت x x # هستند.
۳	۲۰	$ m , q \le 1\ 000$ و همه پرسمان‌ها به صورت x x # یا x x @ هستند.
۴	۵۰	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

4 3 8 4
ab
ac
ba
aaa
# 5 5
@ 2 3
@ 8 7
@ 7 7

خروجی نمونه ۱

I'm a blackboard
c
ca

ورودی نمونه ۲

3 26 1000 2
golabi
saboksar
pashmak
@ 1000 1000
@ 997 997

خروجی نمونه ۲

all
ali

(۲۴امین دوره‌ المپیاد کامپیوتر - آزمون پنجم - ۱۳۹۳/۰۶/۱۵)