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

یک روز یک خری متعلق به مناطق بیابانی به استادیوم فوتبال رفت و به دلیل خرارت(خر بودن) به جای سکوها به داخل زمین رفت. سپس او با دیدن چمن به سر شوق آمد و دیدن هزاران انسان که دور او بودند دو برابر او را ذوق زده کرد؛ احساس کنسرت به او دست داد و تصمیم گرفت که برایشان بخواند(عرعر کند)! او از موسیقی و ریتم چیزی حالی‌اش نبود اما برای اینکه عرعرش ریتمیک باشد تصمیم گرفت که بین عرعرهایش فاصله‌ی مشخصی بیندازد. برای همین او یک عدد $a$ و یک عدد $b$ انتخاب کرد و تصمیم گرفت که اینگونه بخواند:

او در ثانیه‌ی ۰ به مردم اعلام می‌کند که قرار است یک آهنگ درخواستی برایشان بخواند. سپس $a$‌ ثانیه صبر می‌کند و در ثانیه‌ی $a$ عرعر اول را سر می‌دهد. سپس $b$‌ ثانیه صبر می‌کند و در ثانیه‌ی $a+b$ عرعر دوم را سر می‌دهد. بعد دوباره $a$ ثانیه صبر می‌کند و در ثانیه‌ی $2 \times a + b$ عرعر می‌کند. سپس $b$ ثانیه صبر می‌کند و ...

او از اول با خودش قرار گذاشته بود که بیشتر از $l$ بار عرعر نکند. (حنجره‌اش طاقت بیشتر از این مقدار را نمی‌کشد) حالا او $l$‌ بار عرعر کرده است و برایش سوال است که از زمانی که به مردم اعلام کرد که قرار است برایشان بخواند تا الان که آخرین عرعر را سر داده است چند ثانیه گذشته است. او خر است و از شما می‌خواهد که به سوالش جواب بدهید.

ورودی🔗

در تنها سطر ورودی به ترتیب سه عدد $a$ و $b$ و $l$‌ می‌آید که به ترتیب نمایانگر زمان‌های صبر بین عرعرها و تعداد عرعرها می‌باشند. $1 \le a,b,l \le 1000$

خروجی🔗

در تنها خط خروجی زمان آخرین عرعر را چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

1 1 1

خروجی نمونه ۱🔗

1

ورودی نمونه ۲🔗

3 4 5

خروجی نمونه ۲🔗

17

ورودی نمونه ۳🔗

10 3 2

خروجی نمونه ۳🔗

13

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

یک روز یک خری متعلق به مناطق بیابانی به آرایشگاه رفت درحالیکه به دلیل خرارت(خر بودن) فکر می‌کرد که کچل است!!(آخر آن شخصی که در آب می‌بیند که خودش نیست!) آرایشگر موجودی کچل و خودپرست بود؛ درنتیجه از کچل‌ها خوشش می‌آمد؛ اینقدر که در حرف زدنش بعد از هر کلمه‌ای یک بار «کچل!» را به کار می‌برد. همچنین آرایشگر اگر کلماتی را بشنود، همیشه کلمات ثابتی را در جواب آن کلمات می‌گوید و سپس کچل هم می‌گوید؛ به این معنی که مثلا همیشه او در جواب «سلام»، «سلام» می‌گوید و درنتیجه اگر به او «سلام» بگویند او «سلام کچل!» خواهد گفت. (همانطور که می‌دانید آخر هر کلمه یک «کچل!» هم می‌گوید) یا مثلا امکان دارد که در مقابل کلمه‌ای که به او گفته‌ می‌شود هیچ کلمه‌ای را به عنوان جواب نگوید؛ مثلا اگر در جواب «خداحافظ» او چیزی جواب ندهد، اگر به او گفته شود «خداحافظ» او تنها می‌گوید «کچل!» یعنی حتی در این حالت هم او کچل را می‌گوید.

خلاصه بعد از اینکه خر وارد آرایشگاه شد، بزی وارد آرایشگاه می‌شود تا ریش‌هایش را مرتب کند. او در حین وارد شدن به آرایشگاه کلماتی را به آرایشگر می‌گوید. خر قصه‌ی ما اگر چه خر بود اما حافظه‌ی قوی‌ای دارد. از این رو طبق تجربیات قبلی‌اش می‌داند که آرایشگر همیشه به ازای هر کلمه‌ای که به او بگویند چه کلمه‌ای در جواب خواهد گفت. حالا جناب خر می‌خواهد پیش‌بینی کند که آرایشگر چه جوابی به او خواهد داد.(برای فهم بیشتر سوال به مثال‌ها و توضیحاتشان دقت کنید.)

او خر است پس شما باید به سوال او جواب بدهید.

ورودی🔗

در خط اول دو عدد $n$ و $m$ آمده است که به ترتیب نمایانگر تعداد کلماتی است که اگر به آرایشگر گفته شود او جواب خواهد داد و تعداد کلماتی که بز گفته است. سپس در $n$ خط بعدی، در هر خط، دو کلمه آمده است که معنی‌اش این است که اگر کلمه‌ی اول به آرایشگر گفته شود او کلمه‌ی دوم را جواب خواهد داد. سپس در خط آخر $m$ کلمه‌ای که بز به آرایشگر گفته است، آمده است. غیر از $n$ و $m$ که عدد هستند، بقیه کاراکتر‌های ورودی تنها حروف کوچک انگلیسی می‌باشند. همچنین هر کلمه شامل ۱ تا ۱۰ حرف می‌باشد. $1 \le n,m \le 1000$

خروجی🔗

در تنها خط خروجی جواب آرایشگر را به کلمات بز چاپ کنید. دقت کنید که هر بار که آرایشگر بعد از یک جواب می‌خواهد کچل بگوید، یک علامت تعجب(!) هم با آن می‌گوید.

مثال🔗

ورودی نمونه ۱🔗

1 2
salam aleikesalam
salam bache

خروجی نمونه ۱🔗

aleikesalam kachal! kachal!

توضیح: ابتدا آرایشگر جواب کلمه‌ی اول بز (salam) را با کلمه‌ی "aleikesalam" می‌دهد و سپس کچل "!kachal" می‌گوید. بعد هم چون برای کلمه‌ی دوم بز(bache) جوابی ندارد، تنها یک بار کچل "!kachal" می‌گوید.

ورودی نمونه ۲🔗

4 4
kachal kachal
kalache roghane
kalle pache
salam kachal
salam kalache kalle kachal

خروجی نمونه ۲🔗

kachal kachal! roghane kachal! pache kachal! kachal kachal!

توضیح: آرایشگر ابتدا جواب کلمه‌ی اول بز (salam) را با کلمه‌ی "kachal" می‌دهد و سپس کچل می‌گوید. بعد جواب کلمه‌ی دوم بز (kalache) را با کلمه‌ی "roghane" می‌دهد و سپس کچل می‌گوید. پس از آن جواب کلمه‌ی سوم بز (kalle) را با کلمه‌ی "pache" می‌دهد و سپس کچل می‌گوید. در نهایت هم جواب کلمه‌ی آخر بز (kachal) را با کلمه‌ی "kachal" می‌دهد و سپس برای آخرین بار کچل می‌گوید.

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

یک روز یک خری متعلق به مناطق بیابانی سرابی در بیابان دید و به دلیل خرارت(خر بودن) شروع به شنا کردن در آن کرد و از آنجا که بیابان تمامی ندارد، همینطور ادامه داد و ادامه داد. خر ها شیوه خاصی برای شنا کردن دارند که به شنای خری معروف است. اگر بیابان را به صورت یک دستگاه مختصات نشان دهیم که خر از مبدا آن شروع به شنا کرده، خر در اثر شنای خری به این شکل در بیابان جا به جا می‌شود:

• عدد نوشته شده در خانه (x, y) به معنای زمان حضور خر در این خانه است.

مدت ها بعد که خرهای دیگر وقتی متوجه موضوع شدند، به دنبال خر گم‌شده رفتند و در بیابان پخش شدند. حالا هر یک به جایی از بیابان رسیده و می‌خواهد بداند خر گم‌شده چه زمانی در آنجا بوده تا بتواند پیدایش کند. آنها خر هستند و به کمک شما برای گرفتن جواب سوال های خود و پیدا کردن خر گم‌شده احتیاج دارند.

ورودی🔗

در اولین خط ورودی عدد $t$ می‌آید که نشان دهنده تعداد سوالات خرهاست. سپس در $t$ خط بعد در هر خط دو عدد صحیح $x$ و $y$ می‌آیند که مختصات مورد پرسش را نشان می‌دهند.

$1 \le t \le 100$

$0 \le x, y \le 5\ 000$

خروجی🔗

خروجی شامل $t$ خط است به طوری که به ازای هر پرسش باید زمان حضور خر در مختصات مورد پرسش چاپ شود و اگر خر هیچگاه در مسیرش در آن مختصات نبوده عدد 1- چاپ شود.

مثال🔗

ورودی نمونه ۱🔗

3
0 0
3 1
1 1

خروجی نمونه ۱🔗

0
3
1

ورودی نمونه ۲🔗

5
3 3
4 2
2 3
6 4
7 6

خروجی نمونه ۲🔗

5
6
-1
10
-1

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

یک روز یک خری متعلق به مناطق بیابانی به کتابخانه رفت و به دلیل خرارت(خر بودن) به جای مطالعه تصمیم گرفت کتاب ها را گاز بزند. کتابخانه $n$ کتاب دارد که بر حسب موضوعشان با $n$ عدد صحیح متفاوت بین $1$ تا $n$ شماره گذاری شده اند. او می‌خواهد همه کتاب ها را گاز بزند اما می‌خواهد به ترتیبی به گاز زدن بپردازد که حوصله اش سر نرود. از آنجا که هر چه عدد دو کتاب به هم نزدیک تر باشد موضوعاتشان بیشتر شبیه به هم است، در صورتی که خر ما دو کتاب متوالی گاز بزند که اعدادشان کمتر از $k$ تا اختلاف دارند، به دلیل شباهت محتوا حوصله اش سر می‌رود. او خر است و از شما می‌خواهد که ترتیب مناسبی برای گاز زدن به او پیشنهاد دهید.

ورودی🔗

در تنها سطر ورودی به ترتیب دو عدد صحیح $n$ و $k$ می‌آیند که تعداد کتاب ها و عدد مربوط به حوصله خر را نشان می‌دهند. $1 \le k \le n \le 1\ 000\ 000$

خروجی🔗

در تنها خط خروجی باید ترتیب مناسبی از کتاب ها برای این که خر ما گاز بزند چاپ شود و اگر چنین ترتیبی وجود نداشت عبارت "Impossible" چاپ شود.

مثال🔗

ورودی نمونه ۱🔗

5 2

خروجی نمونه ۱🔗

1 4 2 5 3

اگر خر ما کتاب ها را به این ترتیب گاز بزند اختلاف اعداد کتاب های متوالی به ترتیب ۳، ۲، ۳ و ۲ می‌شود و بنابراین اعداد کتاب های متوالی حداقل ۲ تا اختلاف خواهند داشت.

ورودی نمونه ۲🔗

2 2

خروجی نمونه ۲🔗

Impossible

در این صورت چه کتاب ها به ترتیب [2, 1] و چه به ترتیب [1, 2] گاز زده شوند، اختلاف اعداد کتاب اول و دوم کمتر از ۲ می‌شود.

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

یک روز یک خری متعلق به مناطق بیابانی برای کار به کارخانه‌ی لبنیات رفت درحالیکه به علت خرارت(خر بودن) فکر می‌کرد که در کارخانه‌ی لبنیات او می‌تواند پله‌های ترقی را چنتا چنتا طی کند. او پیش مدیر منابع انسانی! کارخانه رفت و او او را به نزد مدیر حمل نقل فرستاد تا از او در حمل و نقل شیرها استفاده کنند اما مدیر حمل و نقل به او گفت که ابتدا باید برای مصاحبه پیش مدیرعامل کارخانه برود. خر قصه‌ی ما رفت پیش منشی مدیرعامل و منشی هم گفت که متاسفانه برنامه‌ی مدیر تا آخر عمرش پر است و وقت ندارد که هیچگاه خر را ملاقات کند. خر هم نگاهی به گوش‌هایش انداخت و دید که دراز است. از این رو حرف منشی را باور کرد و راهش را گرفت و رفت تا از کارخانه بیرون برود. (اگر هنوز از این قصه خوابتان نبرده است به سراغ ادامه‌ی سوال بروم!)

خلاصه خر قصه‌ی ما داشت از در کارخانه بیرون می‌رفت که یک دفعه یک در بازی را دید که رویش نوشته بود: آزمایشگاه. کنجکاوی خر برانگیخته شد و وارد اتاق شد. دید در آنجا شخصی یک لیوان بدست گرفته است و هی نصف محتویات داخل لیوان را می‌خورد و سپس دوباره پر می‌کند. روی لباس آن شخص نوشته شده بود: مدیرعامل. مدیرعامل به محض دیدن خر با شادی فریاد زد و به خر گفت که در ازای اینکه مشکل او را حل کند به او در کارخانه کار می‌دهد. خر هم از این موضوع خرکیف شد و قبول کرد. سپس مدیرعامل شروع به طرح مسئله‌اش کرد: (اگر هنوز از این قصه خوابتان نبرده است به سراغ ادامه‌ی سوال بروم!!)

کارخانه در حال ورشکستگی است و من مجبورم آب قاطی شیر کارخانه بکنم اما می‌خواهم طوری این کار را انجام دهم که مزه‌ی شیر مرا لو ندهد. از این رو آزمایشی طراحی کردم تا ترکیب مناسب را پیدا کنم:

ابتدا نصف یک لیوان را شیر و نصف دیگرش را آب ریختم و محلول را بهم زدم تا خوب یکنواخت شود. سپس نصف لیوان‌ را خوردم و مزه‌اش را تست کردم. اگر مزه‌اش زیادی خوب بود دوباره به اندازه‌ی نصف لیوان آب ریختم و اگر بد بود به اندازه‌ی نصف لیوان شیر ریختم و هم زدم. سپس دوباره نصف لیوان خوردم و مزه‌اش را تست کردم و به لیوان با توجه به مزه‌اش شیر یا آب اضافه کردم. تا الان من $n$ بار این کار را انجام داده‌ام و الان به مزه‌ی دلخواه رسیده‌ام اما نمی‌دانم که در این مدت بیشتر آب خورده‌ام یا شیر تا بتوانم بفهمم که برای تولید انبوه کارخانه به چه نسبتی باید آب و شیر را تهیه کنم. به تو می‌گویم که هر دفعه از این $n$ دفعه، نصف لیوان شیر اضافه کرده‌ام یا آب. تو به من بگو که من شیر بیشتر خورده‌ام یا آب یا هر‌دو را به اندازه‌ی هم خورده‌ام.

مطمئنم که تا الان متوجه شده‌اید که شما باید این سوال را حل کنید!

ورودی🔗

در خط اول ورودی عدد $n$ آمده است که نمایانگر تعداد دفعاتی است که مدیرعامل به لیوان اضافه کرده است. سپس در خط بعدی رشته $s$ با $n$ کاراکتر آمده است که کاراکتر $i$ ام نمایانگر این است که در دفعه‌ی $i$ام چه چیزی به لیوان اضافه شده است. اگر این کاراکتر ‘S’ بود به این معنی است که نصف لیوان شیر اضافه شده است و اگر ‘W’ بود به این معنی است که آب اضافه شده است.

دقت کنید که در ابتدا لیوان به صورت نصف نصف از شیر و آب پر است. سپس مدیرعامل نصف لیوان را می‌خورد. سپس $s_1$ را به لیوان اضافه می‌کند. بعد دوباره نصفش را می‌خورد و همینطور تا آخر که $s_n$ را به لیوان اضافه می‌کند. فقط دقت کنید که بعد اضافه کردن آخر او دیگر نصف لیوان را نمی‌خورد. $1 \le n \le 100\ 000$

خروجی🔗

در تنها سطر خروجی یکی از کلمات زیر را خروجی دهید:

• اگر مدیرعامل بیشتر شیر خورده بود، کاراکتر “S” را خروجی دهید.
• اگر مدیرعامل بیشتر آب خورده بود، کاراکتر “W” را خروجی دهید.
• اگر مدیرعامل به یک اندازه شیر و آب خورده بود، کاراکتر “=” را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

4
WSSS

خروجی نمونه ۱🔗

S

ورودی نمونه ۲🔗

2
SW

خروجی نمونه ۲🔗

S

توضیح: ابتدا مدیرعامل نصف لیوان را می‌خورد که یعنی یک چهارم لیوان شیر و یک چهارم لیوان آب. سپس لیوان را با شیر پر می‌کند و دوباره نصفش را می‌خورد؛ یعنی در مجموع تا الان پنج هشتم لیوان شیر و سه هشتم لیوان آب خورده است. سپس او نصف لیوان آب اضافه می‌کند اما دقت کنید که دیگر نصف لیوان را نمی‌خورد. با توجه به این توضیحات می‌توان گفت که او شیر بیشتر خورده است.

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

یک روز یک خری متعلق به مناطق بیابانی به کازابلانکا رفت درحالیکه به دلیل خرارت(خر بودن) فکر می‌کرد که به کارخانه‌ی شکلات سازی ویلی ونکا رفته‌است!

خر داستان ما تنها یک بار کتاب "چارلی و کارخانه‌ی شکلات‌سازی" را خورده است و خیلی جزییات داستان را به یاد ندارد. به همین دلیل او نمی‌تواند کازابلانکا و این کارخانه‌ را از هم تشخیص دهد. اما حقیقت این است که واقعا تفاوت خیلی زیادی بین این دو وجود ندارد! برای مثال هر دو را می‌توان به شکل محدوده‌ای با $n$ میدان تصور کرد که با $n - 1$ جاده به هم متصل شده‌اند، بصورتی که می‌توان با گذر از تعدادی جاده از هر میدان به هر میدان دیگری سفر کرد. (یعنی ساختار گراف میادین و جاده‌ها یک درخت است.)

در کارخانه‌ی شکلات سازی، این جاده‌ها همگی از شکلات هستند و خر می‌تواند هنگام گذر از جاده‌ها شکلات آن‌ را بخورد. خر ابتدا از شکلات هر جاده (که در واقع گل‌های کف جاده‌های کازابلانکا هستند) یک مقدار تست کرده‌است و برای هر جاده می‌داند که شکلات کف آن جاده چه مقدار خوش‌مزه است. خر پس از جمع کردن این اطلاعات، یک نقشه‌ی جامع تهیه کرد که در آن جاده‌های موجود و خوش‌مزگی شکلات کف هر جاده مشخص شده بود. برخی از این مقادیر خوش‌مزگی منفی بودند که یعنی خر از مزه‌ی شکلات آن خوشش نمی‌آید. (خر کمی به این موضوع شک می‌کند چون او همه‌ی شکلات‌ها را دوست داشت، اما مطالعات اخیر او پیرامون نوشته‌های جان استوارت میل این که اکنون از برخی شکلات‌ها خوشش نمی‌آید را توجیه می‌کرد.)

حال این خر در حال برنامه‌ریزی یک سفر رویایی در این کارخانه‌‌ی اسرارآمیز است. سفر مدنظر خر از یکی از میادین شروع می‌شود و در یک میدان پایان می‌یابد. خر در این سفر مسیر بین این دو میدان را طی می‌کند. (دقت کنید که با توجه به ساختار درختی نقشه، چنین مسیری یکتا است.) همه می‌دانند که خر داستان ما خریست که زمان برایش بسیار مهم است (بدلیل دغدغه‌های کاری) و نمی‌خواهد وقتش تلف شود؛ پس برنامه‌اش را طوری می‌چیند که حتما تعدادی (که ممکن است برابر ۰ باشد) از جاده‌های ابتدای مسیر و یا انتهای مسیر را چهارنعل حرکت کند و شکلات روی جاده‌های این بین (که آن جاده‌ها را چهارنعل نمی‌رود) را بخورد. یعنی به عبارتی یک بازه‌ی پشت سرهم از جاده‌های مسیر را انتخاب می‌کند که شکلات‌هایشان را بخورد و پیش از رسیدن به این بازه و پس از آن را چهار نعل می‌رود. لذتی که او از خوردن این شکلات‌ها می‌برد برابر مجموع خوش‌مزگی آن‌هاست.

حال خر بدلیل ضیق وقت به سراغ شما، از بهترین برنامه‌نویسان جهان، آمده‌است تا از شما تعدادی سوال راجع به برنامه‌ریزی سفرش بپرسد. او ابتدا نقشه‌ی کارخانه‌ی شکلات‌سازی را به شما می‌دهد و سپس $q$ سوال به این شکل از شما می‌پرسد: اگر او بخواهد از میدان $u$ به میدان $v$ سفر کند، بیشترین میزان لذتی که می‌تواند از خوردن شکلات‌ها ببرد چقدر است؟ (دقت کنید که این مقدار همیشه نامنفی است؛ زیرا خر می‌تواند بدون خوردن هیچ شکلاتی با ۰ لذت این مسیر را بپیماید.)

ورودی🔗

در سطر اول ورودی دو عدد طبیعی $n$ و $q$ آمده‌است که به ترتیب نمایانگر تعداد میادین در کار‌خانه‌ی شکلات سازی (یا همان کازابلانکای واقعی!) و تعداد پرسش‌های خر است. میدان‌های کارخانه با اعداد طبیعی ۱ و ۲ و ... و $n$ شماره‌گذاری شده‌اند. $1 \le n, q \le 100\ 000$

سپس در $n - 1$ سطر بعدی توصیف نقشه‌ی تهیه‌شده توسط خر آمده‌است؛ در هریک از این $n - 1$ سطر سه عدد $u$ و $v$ و $d$ آمده‌است که نمایانگر وجود یک جاده بین میادین $u$ و $v$ با میزان خوش‌مزگی شکلات $d$ است.

$1 \le u, v \le n$ $u \neq v$ $|d| \le 10^9$

سپس در هریک از $q$ سطر بعدی، دو عدد طبیعی $x$ و $y$ آمده‌است که نمایانگر شماره میدان دو سر مسیر مورد پرسش خر می‌باشد.

$1 \le x, y \le n$

خروجی🔗

خروجی باید شامل $q$ سطر باشد که هریک شامل تنها یک عدد است. عدد موجود در $i$امین سطر آن خروجی باید نمایانگر پاسخ $i$امین سوال خر باشد.

مثال🔗

ورودی نمونه🔗

7 9
1 2 -4
5 4 -2
5 1 10
2 7 8
3 6 7
7 6 9
7 1
1 2
4 3
5 5
3 4
5 7
7 5
1 1
3 7

خروجی نمونه🔗

8
0
30
0
30
14
14
0
16