+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- شنگدباو در «اینور آب»‌ زندگی می‌کند و خانم کوچولو برای مسافرت به «اونور آب» رفته است!‌ اینور آب و اونور آب خیلی شبیه به هم‌اند. یعنی به ازای هر شهر در اینور آب یک شهر اونور آب مشابه آن وجود دارد و شهر $i$ در اینور آب مشابه شهر $i$ در اونور آب است! بین شهرها در هر دو طرف آب، جاده‌هایی وجود دارد، به طور دقیق تر $n$ شهر وجود دارد و $n-1$ جاده به طوریکه جاده‌ها در هر دو به گونه‌ای هستند که دقیقاً یک مسیر بین هر دو شهر وجود دارد. مسافرت خانم کوچولو $q$ روز طول می‌کشد. در روز $i$ ام او از شهر $u_i$ در اونور آب به شهر $v_i$ از طریق مسیر یکتای بین آن‌ها می‌رود. در این مسیر تعدادی شهر می‌بیند و از این شهرها عکس می‌گیرد. شنگدباو برای اینکه کم نیاورد در همان روز خودش از شهر $a_i$ در اینور آب به شهر $b_i$ از طریق مسیر یکتای بین آنها می‌رود. بعد از هر روز شنگدباو عکس‌هایی که خانم کوچولو در آن روز گرفته را نگاه می‌کند و اگر شهری در این عکس‌ها مشابه شهری بود که خودش در آن روز دیده است می‌گوید:«مام ازینا داریم!» سوال اینجاست که در آخر هر روز شنگدباو چند بار جمله‌ی «مام ازینا داریم!» را می‌گوید. با گرفتن $n$ ،‌ نقشه‌ی اینور آب و اونور آب،‌ به ازای هر روز تعداد دفعات گفتن این جمله‌ها را خروجی دهید. # ورودی در اولین سطر ابتدا $n$ و سپس $q$ آمده است. که $n$ تعداد شهرهای اینور آب و اونور آب است و $q$ برابر تعداد روزهای گردش است. در $n-1$ سطر بعدی دو عدد $u,v$ آمده است که به معنای وجود جاده ای بین دو شهر $u$ و $v$ در اینور آب است. پس از آن نیز مشابهاً جاده‌های اونور آب در $n-1$ سطر آمده است. در $q$ سطر بعدی چهار عدد آمده است که به ترتیب $a_i , b_i , u_i , v_i$ است. $$1 \le n , q \le 300\ 000$$ $$1 \le a_i , b_i , u_i , v_i \le n$$ # خروجی باید $q$ سطر خروجی دهید که سطر $i$ام یک عدد به معنای تعداد دفعاتی است که شنگدباو در روز $i$ام می‌گوید:«مام ازینا داریم!» # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۱۰ | $n , q \le 1\ 000$| | ۲ | ۴۰ | تضمین می‌شود به هر شهری در اینور آب و اونور آب حداکثر دو تا جاده متصل است.| | ۳ | ۵۰ | بدون محدودیت اضافی| # مثال ## ورودی نمونه ``` 5 5 3 4 5 1 4 1 3 2 1 2 4 1 5 1 2 3 4 1 5 5 3 4 2 4 4 3 1 3 1 5 5 3 5 2 1 3 ``` ## خروجی نمونه ``` 0 1 1 2 3 ```

گردش

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

شنگدباو در «اینور آب»‌ زندگی می‌کند و خانم کوچولو برای مسافرت به «اونور آب» رفته است!‌

اینور آب و اونور آب خیلی شبیه به هم‌اند. یعنی به ازای هر شهر در اینور آب یک شهر اونور آب مشابه آن وجود دارد و شهر $i$ در اینور آب مشابه شهر $i$ در اونور آب است! بین شهرها در هر دو طرف آب، جاده‌هایی وجود دارد، به طور دقیق تر $n$ شهر وجود دارد و $n-1$ جاده به طوریکه جاده‌ها در هر دو به گونه‌ای هستند که دقیقاً یک مسیر بین هر دو شهر وجود دارد.

مسافرت خانم کوچولو $q$ روز طول می‌کشد. در روز $i$ ام او از شهر $u_i$ در اونور آب به شهر $v_i$ از طریق مسیر یکتای بین آن‌ها می‌رود. در این مسیر تعدادی شهر می‌بیند و از این شهرها عکس می‌گیرد. شنگدباو برای اینکه کم نیاورد در همان روز خودش از شهر $a_i$ در اینور آب به شهر $b_i$ از طریق مسیر یکتای بین آنها می‌رود.

بعد از هر روز شنگدباو عکس‌هایی که خانم کوچولو در آن روز گرفته را نگاه می‌کند و اگر شهری در این عکس‌ها مشابه شهری بود که خودش در آن روز دیده است می‌گوید:«مام ازینا داریم!»

سوال اینجاست که در آخر هر روز شنگدباو چند بار جمله‌ی «مام ازینا داریم!» را می‌گوید. با گرفتن $n$ ،‌ نقشه‌ی اینور آب و اونور آب،‌ به ازای هر روز تعداد دفعات گفتن این جمله‌ها را خروجی دهید.

ورودی🔗

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

در $n-1$ سطر بعدی دو عدد $u,v$ آمده است که به معنای وجود جاده ای بین دو شهر $u$ و $v$ در اینور آب است. پس از آن نیز مشابهاً جاده‌های اونور آب در $n-1$ سطر آمده است.

در $q$ سطر بعدی چهار عدد آمده است که به ترتیب $a_i , b_i , u_i , v_i$ است.

$1 \le n , q \le 300\ 000$ $1 \le a_i , b_i , u_i , v_i \le n$

خروجی🔗

باید $q$ سطر خروجی دهید که سطر $i$ ام یک عدد به معنای تعداد دفعاتی است که شنگدباو در روز $i$ ام می‌گوید:«مام ازینا داریم!»

زیر مسئله‌ها🔗

زیرمسئله	نمره	محدودیت
۱	۱۰	$n , q \le 1\ 000$
۲	۴۰	تضمین می‌شود به هر شهری در اینور آب و اونور آب حداکثر دو تا جاده متصل است.
۳	۵۰	بدون محدودیت اضافی

مثال🔗

ورودی نمونه🔗

خروجی نمونه🔗

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- شنگدباو *(shengdebao)* معلم یک مهد کودک شده است!‌ هر کدام از بچه‌های این مهد قدرتی دارد،‌ به طور دقیق‌تر قدرت کودک $i$ام برابر $a_i$ است. معضلی که در بین بچه‌ها الان وجود دارد این است که می‌خواهند دو تیم تشکیل بدهند و با هم به بازی «کتک کاری»‌ مشغول شوند! ممکن است تعدادی از بچه‌ها در این بازی شرکت نکنند اما یک نکته که خیلی مورد توجه است این است که اگر قرار باشد تعدادی از بچه ها در تیم اول و تعدادی در تیم دوم باشند جمع قدرت بچه های تیم اول و تیم دوم با هم به پیمانه ی $m$ برابر باشند. شنگدباو به خاطر اینکه به بچه ها درس دوستی و مهربانی بدهد به آنها در حل معضلشان کمک نکرد!‌ اکنون بچه ها پیش شما آمده‌اند و می‌خواهند تعدادی از آنها را در تیم اول و تعدادی در تیم دوم قرار دهید به طوری که جمع قدرت های دو تیم به پیمانه‌ی $m$ برابر شود. به آن‌ها کمک کنید! # ورودی در اولین سطر ابتدا $n$ و سپس $m$ آمده است. که $n$ تعداد بچه ها است. در سطر بعدی $n$ عدد داده شده است که با فاصله جدا شده است. $i$امین عدد $a_i$ است. $$1 \le n \le 1\ 000\ 000$$ $$1 \le m \le 10 ^ 9$$ $$0 \le a_i < m$$ # خروجی اگر روشی برای انجام این کار نبود خروجی دهید: `laelahaellallah` در غیر اینصورت ابتدا خروجی دهید `alhamdolellah` و در سطر بعدی $n$ عدد خروجی دهید که هر کدام برابر $0$ یا $1$ یا $2$ است. اگر $0$ بود یعنی کودک در هیج تیمی نیامده است و اگر $1$ بود یعنی در تیم اول و اگر $2$ بود یعنی در تیم دوم آمده است. توجه کنید باید حداقل یکی از تیم‌ها خالی نباشد،‌ یعنی تمامی اعداد خروجی نباید برابر صفر باشد. ولی ممکن است $1$ یا $2$ نداشته باشیم. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۱۰ | $m \le 1\ 000$| | ۲ | ۶ | $n \le 16$| | ۳ | ۹ | $n \le 20$| | ۴ | ۳۵ | $m \le 1\ 000\ 000$| | ۵ | ۴۰ | بدون محدودیت اضافی| # مثال ## ورودی نمونه ۱ ``` 4 1000 1 4 3 2 ``` ## خروجی نمونه ۱ ``` alhamdolellah 1 0 2 1 ``` ## ورودی نمونه ۲ ``` 4 5 0 1 2 3 ``` ## خروجی نمونه ۲ ``` alhamdolellah 2 0 1 1 ``` ## ورودی نمونه ۳ ``` 3 10000 1 10 100 ``` ## خروجی نمونه ۳ ``` laelahaellallah ```

علی آقا؟!

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

شنگدباو (shengdebao) معلم یک مهد کودک شده است!‌ هر کدام از بچه‌های این مهد قدرتی دارد،‌ به طور دقیق‌تر قدرت کودک $i$ ام برابر $a_i$ است.

معضلی که در بین بچه‌ها الان وجود دارد این است که می‌خواهند دو تیم تشکیل بدهند و با هم به بازی «کتک کاری»‌ مشغول شوند! ممکن است تعدادی از بچه‌ها در این بازی شرکت نکنند اما یک نکته که خیلی مورد توجه است این است که اگر قرار باشد تعدادی از بچه ها در تیم اول و تعدادی در تیم دوم باشند جمع قدرت بچه های تیم اول و تیم دوم با هم به پیمانه ی $m$ برابر باشند.

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

ورودی🔗

در اولین سطر ابتدا $n$ و سپس $m$ آمده است. که $n$ تعداد بچه ها است.

در سطر بعدی $n$ عدد داده شده است که با فاصله جدا شده است. $i$ امین عدد $a_i$ است.

$1 \le n \le 1\ 000\ 000$ $1 \le m \le 10 ^ 9$ $0 \le a_i < m$

خروجی🔗

اگر روشی برای انجام این کار نبود خروجی دهید: laelahaellallah

در غیر اینصورت ابتدا خروجی دهید alhamdolellah و در سطر بعدی $n$ عدد خروجی دهید که هر کدام برابر $0$ یا $1$ یا $2$ است.

اگر $0$ بود یعنی کودک در هیج تیمی نیامده است و اگر $1$ بود یعنی در تیم اول و اگر $2$ بود یعنی در تیم دوم آمده است.

توجه کنید باید حداقل یکی از تیم‌ها خالی نباشد،‌ یعنی تمامی اعداد خروجی نباید برابر صفر باشد. ولی ممکن است $1$ یا $2$ نداشته باشیم.

زیر مسئله‌ها🔗

زیرمسئله	نمره	محدودیت
۱	۱۰	$m \le 1\ 000$
۲	۶	$n \le 16$
۳	۹	$n \le 20$
۴	۳۵	$m \le 1\ 000\ 000$
۵	۴۰	بدون محدودیت اضافی

مثال🔗

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

4 1000 
1 4 3 2

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

alhamdolellah
1 0 2 1

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

4 5 
0 1 2 3

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

alhamdolellah
2 0 1 1

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

3 10000 
1 10 100

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

laelahaellallah

+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- شنگدباو در فراق یار و نبود کار حوصله‌اش سر رفته‌ بود و تصمیم به حل سوالی گرفت. صورت سوال طولانی بود. به قول یکی از دوستان شنگدباو «همیشه که نباید سوالا رو پیچوند! بعضی وقتا باید ساده حرف زد!» در نتیجه تصمیم گرفت حالت ساده شده‌ی صورت سوال را قرار دهد: تعداد $n$ رشته داده شده است، رشته‌ی $i$ام $s_i$ می‌باشد. به ازای هر رشته لیستی از اعداد موجود است، لیست متناظر با رشته‌ی $i$ام شامل $|s_i| + 1$ عدد است که عدد $j$ام آن (با شروع از صفر)‌ مقدار $a_{i,j}$ دارد. ($1 \le i \le n$ ،$0 \le j \le|s_i|$) هزینه‌ی رفتن از رشته‌ی $s_i$ به $s_j$ برابر است با $a_{j , lcp(s_i , s_j)}$ (منظور از $lcp(s , p)$ طول بزرگترین پیشوند مشترک دو رشته‌ی $s$ و $p$ است) فرض کنید روی رشته‌ی $s_A$ قرار داریم و می‌خواهیم به رشته‌ی $s_B$ برسیم. کمینه هزینه برای انجام این‌ کار را باید خروجی دهید.» شنگدباو سوال را حل کرده است! آیا شما هم می‌توانید آن‌ را حل کنید؟ # ورودی در سطر اول ورودی عدد $n$ داده شده است. سپس در $2\times n$ سطر بعدی ابتدا رشته‌ی ناتهی $i$ ام آمده است و سپس لیست متناظر با رشته‌ی مورد نظر آمده‌ است. در سطر آخر نیز ۲ عدد آمده است که اولی $A$ و دومی $B$ است. $$1 \le n \le 500\ 000$$ $$0 \le a_{i,j} \le 10 ^ 9$$ $$\sum |s_i| \le 500\ 000$$ $$A \ne B$$ + رشته های ورودی از حروف کوچک الفبا تشکیل شده‌اند. # خروجی در تنها سطر خروجی کمترین هزینه برای رفتن از $s_A$ به $s_B$ را خروجی دهید. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۲۰ | $n \le 5\ 000$| | ۲ | ۲۰ | به ازای هر $0 \le j < abs(s_i)$ داریم: $a_{i , j+1} - a_{i , j} = 1$| | ۳ | ۲۰ | رشته‌ها فقط از حروف $a$ و $b$ تشکیل شده اند.| | ۴ | ۴۰ | بدون محدودیت اضافی| # مثال ## ورودی نمونه ۱ ``` 3 a 0 1 b 0 1 a 0 1 1 3 ``` ## خروجی نمونه ۱ ``` 0 ``` ## ورودی نمونه ۲ ``` 3 abcd 0 1 2 3 4 abc 0 1 2 3 abcde 0 1 2 10 1 2 2 3 ``` ## خروجی نمونه ۲ ``` 4 ``` ## ورودی نمونه ۳ ``` 4 shengdebao 10 11 12 13 14 15 16 17 18 19 20 bao 4 3 2 7 barricade 1 13 12 11 10 9 8 7 6 5 baran 7 14 3 14 7 6 1 4 ``` ## خروجی نمونه ۳ ``` 6 ```

ال‌سی‌پی

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

شنگدباو در فراق یار و نبود کار حوصله‌اش سر رفته‌ بود و تصمیم به حل سوالی گرفت. صورت سوال طولانی بود. به قول یکی از دوستان شنگدباو «همیشه که نباید سوالا رو پیچوند! بعضی وقتا باید ساده حرف زد!» در نتیجه تصمیم گرفت حالت ساده شده‌ی صورت سوال را قرار دهد:

تعداد $n$ رشته داده شده است، رشته‌ی $i$ ام $s_i$ می‌باشد. به ازای هر رشته لیستی از اعداد موجود است، لیست متناظر با رشته‌ی $i$ ام شامل $|s_i| + 1$ عدد است که عدد $j$ ام آن (با شروع از صفر)‌ مقدار $a_{i,j}$ دارد. ( $1 \le i \le n$ ، $0 \le j \le|s_i|$ )

هزینه‌ی رفتن از رشته‌ی $s_i$ به $s_j$ برابر است با $a_{j , lcp(s_i , s_j)}$ (منظور از $lcp(s , p)$ طول بزرگترین پیشوند مشترک دو رشته‌ی $s$ و $p$ است)

فرض کنید روی رشته‌ی $s_A$ قرار داریم و می‌خواهیم به رشته‌ی $s_B$ برسیم. کمینه هزینه برای انجام این‌ کار را باید خروجی دهید.»

شنگدباو سوال را حل کرده است! آیا شما هم می‌توانید آن‌ را حل کنید؟

ورودی🔗

در سطر اول ورودی عدد $n$ داده شده است. سپس در $2\times n$ سطر بعدی ابتدا رشته‌ی ناتهی $i$ ام آمده است و سپس لیست متناظر با رشته‌ی مورد نظر آمده‌ است. در سطر آخر نیز ۲ عدد آمده است که اولی $A$ و دومی $B$ است.

$1 \le n \le 500\ 000$ $0 \le a_{i,j} \le 10 ^ 9$ $\sum |s_i| \le 500\ 000$ $A \ne B$

رشته های ورودی از حروف کوچک الفبا تشکیل شده‌اند.

خروجی🔗

در تنها سطر خروجی کمترین هزینه برای رفتن از $s_A$ به $s_B$ را خروجی دهید.

زیر مسئله‌ها🔗

زیرمسئله	نمره	محدودیت
۱	۲۰	$n \le 5\ 000$
۲	۲۰	به ازای هر $0 \le j < abs(s_i)$ داریم: $a_{i , j+1} - a_{i , j} = 1$
۳	۲۰	رشته‌ها فقط از حروف $a$ و $b$ تشکیل شده اند.
۴	۴۰	بدون محدودیت اضافی

مثال🔗

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

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

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

3
abcd
0 1 2 3 4
abc
0 1 2 3
abcde
0 1 2 10 1 2
2 3

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

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

4
shengdebao
10 11 12 13 14 15 16 17 18 19 20
bao
4 3 2 7
barricade
1 13 12 11 10 9 8 7 6 5
baran
7 14 3 14 7 6
1 4