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

اصغر پرنده به یک عروسی دعوت شده است. در هنگام شام $n$ نوع غذا روی میز قرار دارند که به ترتیب از ۱ تا $n$ شماره گذاری شده اند. خانواده داماد که بسیار خسیس هستند از مهمان ها بابت شام پول می‌‌گیرند.

تعداد واحد های موجود از غذای $i$ام $L_{i}$، و قیمت هر واحد از آن برابر با $C_{i}$ است. هربار که یک مهمان بشقابی برمی‌‌دارد، باید از غذای شماره ۱ تا غذای شماره $p$ حرکت کند و یک واحد از هر غذایی که تمام نشده بود بردارد و در نهایت $C_{p}$ دلار پول بپردازد. این کار را در صورتی می‌توان انجام داد که از غذای $p$ام حداقل یک واحد موجود باشد.

اصغر گشنه است، قیمت دلار بالا رفته و جمع پول هایی که در جیب و جورابش پنهان کرده روی هم $k$ دلار است. او می‌‌خواهد این پول را به طوری خرج کند که جمع قیمت غذاهایی که می‌‌خورد بیشینه شود. این مقدار بیشینه را به دست آورید.

ورودی🔗

در خط اول ورودی دو عدد $n$ و $k$ آمده اند.

در خط دوم، $n$ عدد که $i$امین آنها $C_{i}$ است، و در خط بعدی هم $n$ عدد که $i$امین‌شان برابر با $L_{i}$ است آمده اند.

$1 \le n \le 40$ $1 \le k \le 64\ 000$ $1 \le C_{i} \le 40$ $0 \le L_{i} \le 40$

خروجی🔗

خروجی برنامه تنها یک عدد است که برابر با بیشینه مقدار مجموع قیمت غذاهاست.

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

مثال🔗

ورودی نمونه🔗

6 8
7 2 3 5 7 2
1 3 0 3 2 1

خروجی نمونه🔗

30

ابتدا از غذای ۱ تا ۶ می‌‌رویم و در طول راه از غذاهای نوع ۱، ۲، ۴، ۵ و ۶ هرکدام یک واحد برمی‌داریم (از غذای نوع ۳ نمی‌‌توان برداشت چون تعدادش ۰ است).

در مرحله بعد از غذای ۱ تا ۴ می‌رویم غذا های نوع ۲ و ۴ را برمی‌داریم.

در مرحله اول ۲ دلار و در مرحله دوم ۵ دلار هزینه کرده ایم که از پولمان که برابر با ۸ است کمتر است.

مجموع قیمت غذاها در مرحله اول برابر با ۲۳ و در مرحله دوم برابر با ۷ است.

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

اصغر پرنده در حال گشت زدن در جای خود بود که یک جایگشت $n$ تایی پیدا کرد. جویای نام جایگشت شد و فهمید که نامش $P$ است و عدد $i$ام آن هم $P_{i}$ است. از آنجایی که اصغر یارانه می‌گیرد و از نظر اقتصادی تامین است، بیکار است و گرافی $n$ راسی می‌سازد و بین رئوس $i$ و $j$ در گراف یال می‌گذارد اگر $(i-j) \times (P_{i}-P_{j})$ کمتر از صفر باشد و همچنین $i$ و $j$ برابر نباشند.

اصغر می‌خواهد مولفه‌های همبندی گرافی که ساخته است را بدست آورد. از آنجایی که اصغر آنقدر هم بیکار نیست و ادمین یکی از چنل‌های تلگرام است از شما می‌خواهد این کار را برایش انجام دهید.

ورودی🔗

در خط اول ورودی عدد $n$ آمده است.

در خط دوم، $n$ عدد که $i$امین عدد نشان دهنده عضو $i$ام جایگشت (یعنی $P_{i}$) است. می‌دانیم که در جایگشت تمام اعداد از ۱ تا $n$ و متفاوت اند.

$1 \le n \le 1\ 000\ 000$

خروجی🔗

در خط اول ورودی تعداد مولفه‌های همبندی گراف را چاپ کنید. در خطوط بعدی، در هر خط باید رئوس یک مولفه را چاپ کنید. عدد اول هر خط نشان دهنده تعداد رئوس مولفه و اعداد بعدی شماره رئوس درون این مولفه اند.

رئوس هر مولفه را بر حسب شماره رأس از کوچکترین به بزرگترین چاپ کنید. مولفه‌ها را به ترتیب کوچکترین رأسشان از کوچکترین به بزرگترین چاپ کنید.

توجه کنید که خروجی یکتاست!

نمره دهی🔗

نمره‌ دهی این سوال به این صورت است که اگر شما $x$ درصد از تست‌ها را درست جواب بدهید نمره شما $x$ خواهد شد.

در ۱/۳ تست‌ها $n$ کمتر از ۱۰۰۰ است.

مثال🔗

ورودی نمونه🔗

4
2 3 1 4

خروجی نمونه🔗

2
3 1 2 3
1 4

گراف دو یال دارد که رئوس (۱,۳) و (۲,۳) را به هم وصل می‌کنند.

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

اصغر پرنده همانطور که از اسمش پیداست در یک درخت زندگی می‌کند. این درخت $n$ راس دارد که با $n-1$ یال به هم وصل شده اند. در هر راس این درخت یک گنده لات نشسته است.

هر گنده لات یکی از اسرار محرمانه دولت را می‌داند (اسراری که لات‌ها می‌دانند متفاوت اند). سازمان امنیت کشور که نمی‌خواهد اطلاعات پخش شود، تمام یال‌های درخت را بسته است.

اکبر چرنده، برادر اصغر، که از نیرو‌های شورشی است تصمیم دارد یال‌ها را باز کند تا اطلاعات پخش شوند. هر روز یا اکبر یک یال بسته را باز می‌کند و یا سازمان امنیت یک یال باز را می‌بندد.

با باز شدن هر یال دو لاتی که در دو سر یال نشسته اند، اسراری که می‌دانند را برای هم فاش می‌کنند و سپس هرکدام اسرار جدیدی که فهمیده اند را برای تمام لات‌هایی که می‌توانند با طی کردن تعدادی یال باز به آنها برسند فاش می‌کنند.

این عملیات تا $m$ روز ادامه پیدا کرد تا اینکه اکبر را توی گونی کرده و بردند. اصغر به ازای هریک از این $m$ روز شماره یالی که وضعیتش تغییر کرده را به شما داده و در نهایت می‌خواهد به ازای $q$ تا از لات‌ها، تعداد اسرار محرمانه ای که می‌دانند را به او بگویید.

ورودی🔗

در خط اول ورودی سه عدد $n$ و $m$ و $q$ آمده‌ اند که تعداد رئوس درخت، تعداد روز‌های عملیات، و تعداد کسانی که اصغر از شما تعداد اسراری که می‌دانند را می‌خواهد را نشان می‌دهند.

در خط $i$ام از $n-1$ خط بعدی، دو عدد $u_{i}$ و $v_{i}$ آمده اند که شماره رئوس دو سر یال $i$ام را نشان می‌دهند. (شماره دو سر یال از ۱ تا $n$ است)

در $m$ خط بعدی شماره یال‌هایی که عملیات روی آنها انجام شده آمده است. (شماره‌ها از ۱ تا $n-1$ است)

و $q$ خط بعدی هم نشان دهنده شماره رئوسی است که باید تعداد اسرار لات‌هایشان را خروجی دهید. این $q$ عدد بین ۱ تا $n$، و متفاوت اند.

$1 \le q \le n \le 100\ 000$ $1 \le m \le 200\ 000$

خروجی🔗

در خروجی باید جواب $q$ درخواست را در خطوط جداگانه چاپ کنید.

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

مثال🔗

ورودی نمونه🔗

5 6 3
1 2
1 3
2 4
2 5
1
2
1
4
4
3
1
4
5

خروجی نمونه🔗

3
5
4

اگر فرض کنیم در ابتدای کار لات شماره $i$ اطلاعات شماره $i$ را دارد، اطلاعاتی که افراد در انتهای این 6 روز می‌دانند به این شکل خواهد بود:

یال شماره 1 باز می‌شود. $(1,2),(1,2),(3),(4),(5)$ یال شماره 2 باز می‌شود. $(1,2,3),(1,2,3),(1,2,3),(4),(5)$ یال شماره 1 بسته می‌شود. $(1,2,3),(1,2,3),(1,2,3),(4),(5)$ یال شماره 4 باز می‌شود. $(1,2,3),(1,2,3,5),(1,2,3),(4),(1,2,3,5)$ یال شماره 4 بسته می‌شود. $(1,2,3),(1,2,3,5),(1,2,3),(4),(1,2,3,5)$ یال شماره 3 باز می‌شود. $(1,2,3),(1,2,3,4,5),(1,2,3),(1,2,3,4,5),(1,2,3,5)$