+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- کاراکتر "من" که دید اکبر بدون اجازه از اسمش در سوال ها استفاده کرده است، تصمیم گرفت انتقام بگیرد. در سرزمین "اکبراینا" درختی کبیر وجود داشت، درخت کبیر درختی ریشه‌دار بی نهایت راس است که هر راس آن دارای 26 فرزند است. امیرمحمد که به نام‌گذاری رئوس درخت علاقه زیادی دارد، به هر راسی از این درخت رشته‌ای از حروف کوچک انگلیسی را متناظر کرد، میدانیم نام‌گذاری امیرمحمد خاصیت های زیر را دارد: + به راس ریشه رشته تهی متناظر شده است. + به هیچ دو راسی رشته یکسان متناظر نشده است. + به ازای هر راسی به جز ریشه اگر رشته متناظر این راس .$s_1 s_2 s_3...s_k$ باشد، رشته متناظر پدر این راس $ s_1 s_2 s_3 ... s_{k-1} $ است. بعد از نام‌گذاری امیرمحمد، امید به وجد آمد و رفت که از راس‌های این درخت بازدید کنه، ولی بعد از مدتی کوتاه فهمید که تو راسی به نام $O$ با یک رشته $m$ حرفی قرار داره و گم شده. برای همین به اکبر (مالک سرزمین و همچنین مالک درخت کبیر) زنگ زد و گفت: "اکبرر بیا منو پیدا کن گم شدم". اکبر که در آن لحظه در راسی به نام $A$ با $n$ حرف قرار داشت، امید خود را از دست نداد و به سمت امید دوید، او می‌توانست در هر ثانیه از یک راس به یکی از راس های مجاورش برود، و چون خیلی نگران از بین رفتن امیدش بود، در کوتاه ترین زمان ممکن امید خود را بدست آورد. حال شما به عنوان شنونده این داستان پندآموز به ما اعلام کنید که اکبر چند ثانیه پس از حرکت، امید خود را بدست می آورد. توجه‌کنید که ساختار نام‌گذاری راس‌های درخت مانند درخت پیشوندی است که برای پیداکردن مطالب بیشتر در این مورد می‌توانید به [این‌جا](https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA_%D9%BE%DB%8C%D8%B4%D9%88%D9%86%D8%AF%DB%8C) مراجعه کنید. # ورودی در خط اول ورودی عدد $n$ آمده است. در خط دوم ورودی رشته ی $A$ دارای $n$ حرف از حروف کوچک الفبای انگلیسی آمده است. در خط سوم ورودی عدد $m$ آمده است. در خط چهارم ورودی رشته ی $O$ دارای $m$ حرف از حروف کوچک الفبای انگلیسی آمده است. $$1 \le n, m \le 100\ 000$$ # خروجی در تنها خط خروجی یک عدد که نشان دهنده پاسخ مسئله است را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 ab 2 ac ``` ## خروجی نمونه ۱ ``` 2 ``` اکبر در ثانیه اول از $ab$ به $a$ میرود، و در ثانیه دوم از $a$ به $ac$ میرود و امیدش با بدست می‌آورد. ## ورودی نمونه ۲ ``` 3 aab 3 aba ``` ## خروجی نمونه ۲ ``` 4 ``` اکبر در ثانیه اول از $aab$ به $aa$ می‌رود، در ثانیه دوم از $aa$ به $a$ می‌رود، در ثانیه سوم از $a$ به $ab$ می‌رود، در ثانیه چهارم از $ab$ به $aba$ می‌رود و امیدش با بدست می‌آورد.

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