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

در شهر آبابوا به دنباله، امیرمحمد می‌گویند، هم‌چنین به دنباله‌هایی که به ازای هر $i$ که 1 < $a_i$ حداقل یکی از دو عدد $a_i$ و $a_i-1$ سمت چپ مکان $i$ ظاهر نشده باشند، ایمانی می‌گویند. (منظور از سمت چپ، تمام خانه‌های قبل از خانه $i$ است، نه تنها خانه‌ی قبلی)
مثلا $<2, 2, 1>$ یک امیرمحمد ایمانی معتبر است و $<1, 2, 2>$ یک امیرمحمد ایمانی معتبر نیست.
اهالی شهر آبابوا به سوالی مهم برخورده‌اند و از شما درخواست کمک دارند: چند امیرمحمد ایمانی به طول $n$ با اعداد $1$ تا $m$ داریم؟

ورودی🔗

سطر اول وروی شامل دو عدد $n$ و $m$ است که $n$ طول مورد‌نظر برای امیرمحمد ایمانی است و امیرمحمد ایمانی فقط می‌تواند شامل اعداد $1$ تا $m$ باشد. $1 \le n, m \le 500$

خروجی🔗

در خروجی باید تنها یک عدد چاپ کنید که جواب سوال مردم آبابوا است. از آنجا که این عدد می‌تواند خیلی بزرگ باشد باقی‌مانده آن بر $10^9 + 7$ را چاپ کنید.

زیر مسئله ها🔗

مثال🔗

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

2 2

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

4

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

3 2

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

6

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

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

می‌دانیم که خانه پسر $i$ ام در شهر $a_i$ و خانه دختر $j$ام در شهر $b_j$ است؛ هزینه رفتن از شهر $x$ به شهر $y$ برابر $|x - y|$ است. همچنین در صبح هر یک از روزهای $1$ تا $q$ یکی از پسران یا دختران به دلیل وضعیت بد مالی خانه‌ی خود را تغییر می‌دهد و به خانه جدیدی می‌رود (ممکن است خانه جدید در هر شهری باشد).

بر طبق آداب و رسوم ما ایرانی‌ها بدیهی است که مراسم خواستگاری در شب صورت می‌گیرد و همچنین هیچ دو نفری در یک شب خواستگاری یک نفر نمی‌روند و همچنین پول برگشت پسر به خانه را پدر دختر تقبل می‌کند. حال شما به ازای هر یک از روزهای $1$ تا $q$ بگویید که اگر پسرها بخواهند در شب این روز به خواستگاری بروند کمترین هزینه‌ای که مجموعا سلطان برای آن‌ها باید پرداخت کند چه‌قدر خواهد بود؟

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

ورودی🔗

در سطر اول ورودی عدد $n$ آمده است که نشان‌دهنده تعداد پسرها و همچنین تعداد دخترها است.
سپس در سطر بعدی $n$ عدد آمده است که عدد $i$ام همان $a_i$ است.
در سطر بعدی نیز $n$ عدد آمده است که عدد $j$ ام نمایانگر $b_j$ است.
در سطر چهارم ورودی عدد $q$ آمده است که نشان‌دهنده‌ی تعداد روزهایی است که پسرهای سلطان عزم خواستگاری می‌کنند.
در $q$ سطر بعدی نیز در هر سطر دو عدد $v_d$ و سپس $x_d$ آمده است که نشان‌دهنده‌ی مهاجرت نفر $v_d$در ابتدای روز فعلی به خانه‌ای در شهر $x_d$ می‌باشد.
اگر $v_d$ بزرگتر از $n$ باشد، منظور دختر $v_d - n$ ام و در غیر این صورت منظور پسر $v_d$ام است.

• $1 \le n, q \le 10^{5}$
• $1 \le a_i, b_j, x_d \le 10^{5}$
• $1 \le v_d \le 2 \times n$

خروجی🔗

در خروجی $q$ عدد چاپ کنید که عدد $d$ام نشان‌دهنده کمترین مجموع هزینه رفتن پسرهای سلطان به خواستگاری در شب روز $d$ام است.

زیر مسئله ها🔗

مثال🔗

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

2
2 100
1 101
2
1 1
4 100

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

1
0

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

5
10 2 20 3 30
5 17 4 9 23
6
4 9
9 7
8 15
1 47
5 21
2 8

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

17
19
20
47
38
38

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

امیرمحمد یک گراف وزن‌دار همبند $n$ راسی با $m$ یال ($m > n$) دارد. در گراف وزن یال بین دو راس $x$ و $y$ را با $w_{x,y}$ نمایش می‌دهیم.
او شروع به بازی با این گراف می‌کند. در هر گام یک راس مثل $x$ که درجه‌اش دقیقا $2$ است (یعنی دو یال به این راس متصل است) و دو همسابه متمایز $y$ و $z$ دارد را انتخاب می‌کند و این راس و یالهای متصل به آن را حذف می‌کند. سپس یک یال بین دو راس $y$ و $z$ با وزن $max(w_{x,y}, w_{x, z})$ قرار می‌دهد. اما امیرمحمد خیلی کنترلی روی اعصابش ندارد و یک راس تصادفی $x$ انتخاب می‌کند و عملیات بالا را روی آن انجام می‌دهد (با احتمال یکسان بین انتخاب های ممکن).
می‌دانیم امیرمحمد $k$ بار این کار را انجام داده است. امید ریاضی مجموع وزن یال‌های درخت فراگیر کمینه (MST) گراف حاصل را پس از انجام $k$ مرحله بیابید.
فرض کنید پاسخ به صورت $\frac{P}{Q}$ باشد که $gcd(P, Q) = 1$. شما حاصل $P \times Q^{-1} \mod (10^9 + 7)$ را نمایش دهید.
تضمین می‌شود که در گراف داده شده در هر حالتی می‌توان $k$ بار چنین عملیاتی را انجام داد.

ورودی🔗

سطر اول ورودی شامل سه عدد $n$ و $m$ و $k$ است. سپس در $m$ سطر بعدی، در هر سطر سه عدد $u_i$ و $v_i$ و $w_i$ آمده است که بیانگر یک یال بین $u_i$ و $v_i$ با وزن $w_i$ است.

• گراف در ابتدا یال چندگانه ندارد ولی ممکن است پس از انجام عملیات گفته‌شده یال چندگانه به‌وجود بیاید.
• $1 \le k < n < m \le 5 \times 10^{5}$
• $m <= \frac{n \times (n-1)}{2}$
• $1 \le u_i, v_i \le n$
• $1 \le w_i \le 10^9$
• $u_i \neq v_i$

خروجی🔗

در تنها سطر خروجی خواسته مسئله را چاپ کنید.

زیر مسئله ها🔗

مثال🔗

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

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

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

4

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

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

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

12

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

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

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

500000006

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

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

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

9