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

آقای $B$ می‌خواهد با دعوت تعدادی از کارمندهای شرکتش یک دوره مهمانی مخفیانه برگزار کند.

اگر این شرکت $n$ کارمند داشته باشد، این کارمندها با شماره‌های $1$ تا $n$ مشخص می‌شوند و فرد شماره $i$ با افراد با شماره‌های $2i$، $2i+1$ و $\lfloor \frac{i}{2} \rfloor$ در صورت وجود دوست است.

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

حال آقای $B$ می‌خواهد تعدادی از کارمندهایش را به مهمانی دعوت کند، او برای انتخاب افراد در شب اول یکی از مجموعه‌های ناتهی کارمندان را به صورت تصادفی و با احتمال برابر انتخاب و دعوت می‌کند. (یعنی هر کدام از $2^n-1$ حالت ممکن به احتمال برابر انتخاب می‌شوند)

آقای $B$ از شما خواسته تا امیدریاضی ناراحتی کلی افراد را برای او محاسبه کنید ولی چون یادش نیست که شرکتش چند کارمند دارد $q$ حدس مختلفی که برای $n$ دارد را به شما می‌گوید تا جواب را در همه حالات به دست آورید. همچنین چون او اعداد اعشاری را دوست ندارد، از شما خواسته که اگر امید ریاضی خواسته شده به صورت $\frac{P}{Q}$ نوشته شود که $P$ و $Q$ اعداد صحیح نسبت به هم اول هستند، با توجه به این که $Q$ بر $10^9+7$ بخش‌پذیر نیست، مقدار $PQ^{-1}$ به پیمانه $10^9+7$ را به عنوان جواب گزارش کنید.

ورودی🔗

در سطر اول ورودی عدد $q$ آمده‌است.

در هر یک از $q$ سطر بعدی یک مقدار $n$ آمده است که تعداد کارمندان شرکت در این سناریو را نشان می‌دهد. $1 \le q \le 2000$ $1 \le n \le 10^{18}$

خروجی🔗

در هر یک از $q$ خط خروجی, مقدار خواسته شده را برای $n$ مربوطه خروجی دهید.

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

مثال🔗

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

5
1
2
3
4
5

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

0
666666672
571428577
733333341
548387104

در حالت $n = 1$ امید ریاضی ناراحتی کلی افراد برابر $0$ است. برای $n=2$ امید ریاضی برابر $\frac{2}{3}$ است که به پیمانه $10^9+7$ برابر با $666666672$ است.

امید ریاضی ناراحتی کلی افراد در مثال‌های داده شده به صورت زیر است:

$\frac{0}{1} \frac{2}{3} \frac{11}{7} \frac{38}{15} \frac{105}{31}$

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

5
438683104447824131
461983238699791439
483227912528828095
352592111888489755
432980889538354445

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

597802608
929243282
897893632
550955255
88788769

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

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

در این مسئله دنباله‌ای از اعداد صحیح به طول $n$ به شما داده می‌شود و شما باید با حداقل تعداد عملیات ممکن همه‌ی اعداد دنباله را تبدیل به صفر کنید. اعداد این دنباله از چپ به راست $a_1$ تا $a_n$ نامیده می‌شوند.

هر عملیات به این صورت است که ابتدا یک بازه از دنباله مانند $[l, r)$ انتخاب می‌کنید و از همه‌ی اعضای این بازه ۱ واحد کم می‌کنید. ($1 \le l < r \le n + 1$)

• طول هر بازه که انتخاب می‌کنید باید توانی از ۲ باشد.
• هر بازه حداکثر ۱ بار می‌تواند انتخاب شود.
• اگر دو بازه‌ی انتخاب شده مانند $[l_2, r_2)$ و $[l_1, r_1)$ وجود داشته باشند که اشتراکشان تهی نباشد، آنگاه $max(l_1 - l_2, l_2 - l_1)$ باید مضربی از $min(r_1 - l_1, r_2 - l_2)$ باشد.

ورودی🔗

در خط اول ورودی، عدد طبیعی $n$ آمده‌است که طول دنباله را نشان می‌دهد.

در خط بعدی، $n$ عدد حسابی آمده است که به ترتیب $a_1$ تا $a_n$ را نشان می‌دهند.

$1 \le n \le 10^5$ $0 \le a_i \le 10^5 (1 \le i \le n)$

خروجی🔗

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

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

مثال🔗

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

10
1 1 1 1 2 2 2 3 2 1

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

5

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

8
2 2 2 0 1 1 2 2

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

-1

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

مهرشاد یک میوه فروشی دارد که فقط پرتقال می‌فروشد. او پرتقال ها را در $q$ کیسه داخل انبار نگه‌داری می‌کند؛ این کیسه‌ها با اعداد $1$ تا $q$ شماره‌گذاری شده‌اند. درون کیسه‌ی $i$ام، $x_i$ پرتقال وجود دارد.

او امروز تصمیم گرفته که همه‌ی کیسه‌ها را جلوی مغازه داخل یک ردیف بچیند. برای این کار، در مرحله‌ی $i$ام کیسه‌ی $i$ام را برمی‌دارد و پشت $p_i$امین کیسه‌ی پرتقال می‌گذارد(اگر $p_i = i$ باشد، کیسه‌ی $i$ام جلوی تمامی کیسه‌های موجود در صف قرار می‌گیرد.) ؛ سپس تمام کیسه‌های جلوی آن را یک واحد به جلو هل می‌دهد. به طور مثال اگر $p_4 = 2$ باشد، پیش از مرحله‌ی ۴ام در صف ۳ کیسه قرار دارد. پس از این مرحله، کیسه‌ی شماره‌ی ۴ بین کیسه‌ی اول و دوم قرار می‌گیرد. همچنین اگر $p_4 = 4$ باشد، کیسه‌ی شماره‌ی ۴ جلوی تمام کیسه‌ها قرار می‌گیرد.

او این کار را آن قدر تکرار می‌کند تا کیسه های داخل انبار تمام شوند. مهرشاد بعد از هر عملیاتی که انجام می‌دهد، برایش سوال می‌شود که «طول بزرگ‌ترین زیردنباله‌ی اکیداً صعودی(LIS) صف کیسه‌ها چند است؟» امّا از آن جایی که او سخت درگیر کار و کاسبی‌ش است و وقت سر خاراندن هم ندارد، شما باید به سوالاتش پاسخ دهید. یک دنباله مثل $b_1, b_2, b_3, \cdots, b_i$ زیردنباله‌ای از صف پرتقال ها است اگر و فقط اگر، بتوان با حذف تعدادی دلخواه از کیسه ها به ردیفی از کیسه‌ها رسید که تعداد پرتقال‌های درونشان به ترتیب برابر با دنباله‌ی $b$ باشد.

ورودی🔗

در خط اول ورودی$q$، تعداد کیسه‌های درون انبار می‌آید.

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

$1 \leq p_i \leq i$ $1 \le q \le 10^{6}$ $\sum x_i \leq 10^6$ $1\leq x_i \leq 10^6$

خروجی🔗

به ازای هر عملیات مهرشاد، اندازه‌ی بزرگ‌ترین زیردنباله‌ی صعودی صف پرتقال‌ها را چاپ کنید.

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

مثال🔗

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

6
1 7
2 10
2 11
2 8
4 10
1 2

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

1
2
2
3
3
4

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

4
1 3
2 1
1 1
2 2

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

1
1
2
3

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

اکبر یک بازی Crawler Dungeon جدید به اسم Keys! خریده است. او آن قدر معتاد این بازی شده است که چندین ساعت به طور متوالی آن را بازی کرده است.

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

بازی از اتاق $s$ شروع می‌شود، و اکبر باید به اتاق $t$ برود که ورودی Dungeon بعدی است.

اما $m$ تا از این در‌ها قفل هستند که کلید‌های آن‌ها می‌توانند در اتاق‌های دیگری باشند. شخصیت اکبر در بازی تنها توانایی حمل یک کلید را دارد و اگر کلیدی را برداشت، تا زمانی که در متناظر با آن کلید را باز نکند نمی‌تواند آن کلید را زمین بگذارد.

همچنین 1 ثانیه طول می‌کشد که شخصیت اکبر از یک اتاق به اتاق مجاورش برود. توجه کنید که اگر یک در را با کلید باز کنیم، شخصیت اکبر به اتاق بعدی نمی‌رود و در همان اتاق باقی می‌ماند؛ این فرایند، زمان نمی‌برد و بلافاصله انجام می‌شود. رکورد اکبر در این بازی در واقع مدت زمانی است که طول می‌کشد از $s$ به $t$ برود.

اکبر که خیلی این بازی را دوست دارد، دلش می‌خواهد که رکورد جهانی این بازی را بزند! برای همین از شما خواسته برنامه‌ای بنویسید که با ورودی گرفتن درخت مربوط به Dungeon و اطلاعات کلید‌ها، کمینه زمان مورد نیاز برای رفتن به Dungeon بعدی را خروجی بدهد.

ورودی🔗

در خط اول $n$ آمده است، که تعداد اتاق‌های Dungeon اکبر را مشخص می‌کند.

در خط بعدی اعداد $s$ و $t$ آمده‌اند، که به ترتیب مربوط به اتاق شروع Dungeon و اتاق ورودی Dungeon بعدی است.

در $n-1$ خط بعدی، اطلاعات مربوط به در‌ها و کلید‌ها به صورت $u\:v\:w$ آمده است که به این معنی است یک در بین اتاق $u$ و $v$ وجود دارد. همچنین اگر $w=0$ باشد، به این معنی است که این در قفل نیست و در غیر این صورت به این معنی است که این در قفل است و کلید آن در اتاق $w$ قرار دارد.

$1 \leq n \leq 10^6$ $1 \le s,t,u,v \le n$ $0 \le w \le n$ $0 \leq m \leq 20$

خروجی🔗

در تنها خط خروجی، کمینه زمان مورد نیاز اکبر برای این که از $s$ به $t$ برود را چاپ کنید.

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

مثال🔗

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

4
1 4
1 2 0
1 3 2
3 4 1

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

4

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

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

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

10

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

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

برای مثال اگر اعداد روی هندوانه‌ها $\langle 1, 5, 2, 4, 6,3\rangle$ باشد، بعد از یک روز تبدیل به $\langle 5, 6 ,3\rangle$ و بعد از یک روز دیگر تبدیل به $\langle 6 , 3\rangle$ می‌شود و در روزهای بعدی تغییری نمی‌کند. در این مثال، ابوالفضل هندوانه‌های اول (با شماره‌ی $1$)، سوم (با شماره‌ی $2$) و چهارم (با شماره‌ی $4$) را در روز اول، و هندوانه‌ی دوم (با شماره‌ی $5$) را در روز دوم می‌خورد و هندوانه‌های پنجم (با شماره‌ی $6$) و ششم (با شماره‌ی $3$) را هرگز نمی‌خورد.

یک عدددهی به هندوانه‌ها «ابوالفضل‌پسند» است اگر به ازای هر $i$ در صورتی که $b_i = -1$ باشد هندوانه‌ی $i$ام هیچ‌وقت خورده نشود و در غیر این صورت در روز $b_i$ خورده شود. به ابوالفضل $k$امین زیباترین عدددهی ابوالفضل‌پسند را بگویید.

یک جایگشت $p_1, p_2, ..., p_n$ از جایگشت $q_1,q_2,...,q_n$ زیبا‌تر است اگر مقدار $i$ وجود داشته باشد که به ازای هر $j < i$ جایگاه $k$ وجود داشته باشد که $p_k = j$ و $q_k = j$ و اگر $p_x = i$ و $q_y = i$ باشد، $x < y$ نیز برقرار باشد.توجه کنید که زیباتر بودن با کوچک‌تر بودن از نظر کتاب‌خانه‌ای تفاوت دارد.

می‌توان اثبات نمود که اگر جایگشت $p$ از جایگشت $q$ و جایگشت $q$ از جایگشت $r$ زیباتر باشد، آن‌گاه جایگشت $p$ از جایگشت $r$ نیز زیباتر است.

ورودی🔗

در خط اول ورودی $n$، تعداد هندوانه‌ها و سپس $k$ به ترتیب می‌آیند.

در خط بعدی $n$ عدد $b_1, b_2, ..., b_n$ به‌ترتیب می‌آیند.

$1 \le n \le 10^{5}$ $1 \le k \le 10$ $-1 \leq b_i \leq n$ $b_i \neq 0$

خروجی🔗

اگر کمتر از $k$ عددگذاری ابوالفضل‌پسند وجود داشت $-1$ و در غیر این صورت $k$امین زیبا‌ترین عددگذاری ابوالفضل‌پسند را خروجی دهید.

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

مثال🔗

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

5 1
1 2 1 -1 -1

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

1 3 2 5 4

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

5 2
1 2 1 -1 -1

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

1 4 2 5 3

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

5 10
1 2 1 -1 -1

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

-1

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

«شرکت تولیدی دبّه‌ی آقای موز و دوستان» معروف به «شتدآمود» یکی از خوش‌نام‌ترین کارخانه‌های دبّه‌سازی است که همه ساله روز قبل از امتحانات عملی، از دبّه‌های جدیدش رونمایی می‌کند.

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

منظور از رشته، دنباله‌ای متشکّل از حروف کوچک انگلیسی است.

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

مثلا اگر آقای موز دو رشته‌ی tanin، یک رشته‌ی qosxyz و یک رشته‌ی ehtemal به کارگرانش بدهد، آن‌ها می‌توانند با حذف پسوندی از هر رشته، چهار رشته‌ی qos، tan، tani و eh را بسازند و با پشت سر هم قرار دادن آن‌ها رشته‌ی qostantanieh را تولید کنند.

در مغازه‌ی رشته فروشی $n$ نوع رشته و از هر نوع رشته به تعداد نامحدود وجود دارد. این رشته‌ها را با $t_1, t_2, \cdots, t_n$ نمایش می‌دهیم. هزینه‌ی خرید هر یک از این رشته‌ها هم $1$ ریال است.

هم‌چنین در دوره‌ی تابستانه(پاییزه؟) $m$ دانش‌پژوه وجود دارند؛ آقای موز رشته‌ی بزرگی(به طول $L$) به نام $S$ دارد و به ازای $m$ زیررشته از $S$ که با $[l_i, r_i)$ مشخّص می‌شوند($1 \le i \le m$)، می‌خواهد رشته‌ای برابر با آن زیررشته تولید کند و به دانش‌پژوه $i$ام هدیه دهد. دقّت کنید حروف هر رشته به طول $L$ از چپ به راست با اعداد $0$ تا $L - 1$ شماره‌گذاری می‌شوند و زیررشته‌ی $[l, r)$ نشان‌دهنده‌ی زیررشته‌ای است که از کنار هم قرار دادن حروف $l$ تا $r - 1$ آن رشته(به ترتیب) ایجاد می‌شود.

به آقای موز بگویید که کم‌ترین هزینه‌ی مورد نیاز برای تامین هدیه‌ی هر دانش‌پژوه چند ریال است.

ورودی🔗

در خط اول ورودی دو عدد $n$ و $m$ آمده است که به ترتیب تعداد رشته‌های داخل رشته‌فروشی و تعداد دانش‌پژوهان دوره‌ی تابستانه است.

در خط $i$ام از $n$ خط بعد، رشته‌ی $t_i$ آمده است. این رشته‌ها، رشته‌های موجود در مغازه‌ی رشته‌فروشی هستند.

پس از آن نیز رشته‌ی $S$ آمده است.

در خط $i$ام از $m$ خط بعد نیز دو عدد $l_i$ و $r_i$ آمده است که نشان‌دهنده‌ی بازه‌ی مربوط به هر دانش‌پژوه است.

$1 \le L, m \le 300\ 000$ $1 \le n \le 10\ 000$ $0 \le l_i < r_i \le L$

مجموع طول $t_i$ ها نیز حداکثر $500\ 000$ است.

خروجی🔗

خروجی می‌بایست متشکّل از $m$ خط باشد. در $i$امین خط، کم‌ترین هزینه‌ای که برای تولید رشته‌ی مربوط به دانش‌پژوه $i$ام نیاز است را چاپ کنید. هم‌چنین اگر این کار ممکن نیست، $-1$ چاپ کنید.

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

مثال🔗

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

3 13
ab
ac
aef
abaaceaef
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
1 2
6 9
5 9
4 9

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

1
1
2
3
3
-1
-1
-1
-1
-1
1
-1
-1

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

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

پدرام برای کمک به شما، توضیحی در مورد زیر گراف القایی به شما داده است:

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

زیردرخت القایی ، یک زیرگراف القایی است، که راس‌ها و یال‌هایش تشکیل یک درخت بدهد.

ورودی🔗

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

در هر یک از $m$ خط بعدی دو عدد که نمایانگر دو سر یک یال‌اند، آمده است. $1 \le n \le 10^5$

خروجی🔗

در تنها سطر خروجی، باقی مانده‌ی عددی که پدرام می‌خواهد را به $10^9+7$ چاپ کنید.

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

مثال🔗

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

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

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

19

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

5 4
1 2
1 3
2 4
2 5

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

17

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

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

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

52

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

یاسین در یک فستیوال شرکت کرده است. در این فستیوال، رسم است که به درخت مقدّس برچسب آویزان می‌کنند؛ روی هر برچسب یک عدد حسابی نوشته شده است. اما متاسفانه یاسین زود آمده بود و هنوز کسی به درخت‌ها چیزی وصل نکرده بود.

پیرمردی که داشت از کنار درخت رد می‌شد، یاسین را می‌بیند و تصمیم می‌گیرد که او را کمی اذیت بکند! او یک برچسب به ریشه‌ی درخت وصل می‌کند که روی آن عدد $r$ نوشته شده است. سپس رو به یاسین می‌کند و به او می‌گوید که اگر بتواند تعداد حالات برچسب چسباندن به بقیه‌ی رئوس را بشمارد به او شکلات می‌دهد.

سپس پیرمرد کمی فکر می‌کند و می‌گوید: «عه ببخشید یه شرطش رو یادم رفت بگم.» شرط اضافه‌ی پیرمرد این بود که مجموع اعداد فرزندان هر راس، نباید از عدد برچسب خود آن راس بیشتر بشود. مثلا اگر از یک راس برچسب $3$ آویزان باشد و آن راس $2$ فرزند داشته باشد که به یکی از آن‌ها برچسب $1$ آویزان است، عدد برچسب فرزند دیگر حداقل $0$ و حداکثر $2$ خواهد بود.

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

یاسین که خیلی گرسنه است، از شما می‌خواهد کمکش کنید که بتواند سوالات پیرمرد را جواب دهد و به هر قیمتی شکلات را از او بگیرد!

دقت کنید منظور از فرزندان یک راس، تمام رئوسی است که با یک یال مستقیما به آن راس متّصل شده‌اند و پدر آن راس نیستند.

ورودی🔗

در خط اول ورودی، دو عدد طبیعی $n$ و $r$ آمده‌است که به ترتیب تعداد راس‌های درخت و عدد برچسب ریشه را نشان می‌دهند.

در $n-1$ خط بعدی، یال‌های درخت آمده‌است. هر یک از این $n-1$ خط دارای دو عدد طبیعی مانند $v$ و $u$ است که نشان دهنده وجود یال بدون جهت $u \leftrightarrow v$ در درخت یاسین است. توجه کنید که ریشه‌ی درخت همیشه راس 1 است.

در خط بعد $q$ آمده است که تعداد پرسش‌های پیرمرد را نمایش می‌دهد.

در $q$ خط بعدی، سوال‌ها با فرمت $1\:v\:x$ یا $2\:v$ آمده‌اند؛ $v$ یک راس غیر ریشه است و $0 \le x \le r$ عدد روی برچسبی که به $v$ وصل می‌شود است. سوال اول مربوط به اضافه کردن یک برچسب به رأس $v$ با عدد $x$ است و سوال دوم مربوط به حذف برچسب از رأس $v$.

$1 \le r \le 3 \times 10^5$ $1 \le n \le 2 \times 10^5$ $0 \le q \le 2 \times 10^5$

سوال نوع اول: $2 \le u \le n$ و $0 \le v \le r$

سوال نوع دوم: $2 \le u \le n$

تضمین می‌شود که عملیات نوع اول روی رئوسی که برچسب ندارند انجام شود و عملیات نوع دوم روی رئوسی که برچسب دارند.

خروجی🔗

در خط $i$ام از $q+1$ خط خروجی، باقی‌مانده‌ی تعداد حالات انجام این کار بعد از عملیات $i-1$ام را بر $10^9+7$ چاپ کنید. در واقع اول در یک خط پاسخ را با فرض وجود تنها برچسب ریشه چاپ کنید و در خط‌های بعدی پاسخ مربوط به هر عملیات را چاپ کنید.

توجه کنید که ممکن است خروجی صفر باشد!

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

مثال🔗

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

3 2
1 2
2 3
2
1 2 1
2 2

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

6
2
6

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

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

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

70
4
1
0

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

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

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

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

• عدد $x$ به اعداد روزهای $l$ تا $r$ اضافه شود.
• عدد $-1$ در اعداد روزهای $l$ تا $r$ ضرب شود.
• تعداد زیررشته‌های زیگزاگی روز‌های $l$ تا $r$ چندتا است.

دقت کنید که تمام تغییرات و سوالات شامل دو سر بازه خود می‌شوند، درواقع خود $l$ و $r$ نیز داخل بازه هستند. حال به محمد کمک کنید که پاسخ سوال‌هایش را پیدا کند تا زودتر بتواند مهاجرت کند و به آرزوهایش برسد و شما برای همیشه از سوال‌های او راحت شوید.

یک دنباله مثل $b_1, b_2, b_3, \cdots, b_k$ زیررشته‌ای از آرایه وقت‌های باز شده سفارت است اگر و فقط اگر، بتوان با حذف تعدادی دلخواه از روزها از انتها و ابتدای آرایه، این زیر رشته به دست آید.

یک دنباله مثل $b_1, b_2, b_3, \cdots, b_k$ زیگزاگی است اگر و تنها اگر یکی از دو شرط زیر را داشته باشد:

• $b_1 < b_2 > b_3 < b_4 > \cdots$
• $b_1 > b_2 < b_3 > b_4 < \cdots$

ورودی🔗

در خط اول ورودی $n$ و $q$، تعداد روزهایی که محمد برای آن‌ها اطلاعات به دست آورده و مجموع تغییرات و سوالات می‌آید.

در خط دوم ورودی $a_1, a_2, \cdots, a_n$، که برابر با تعداد وقت‌های ملاقات باز شده توسط سفارت در هر روز است.

در خط $i$ام از هر یک از $q$ خط بعدی، ابتدا $t_i \in \{+, *, ?\}$ آمده است که $+$ به معنای عملیات نوع اول بر روی داده‌ها است، $*$ نشان دهنده عملیات نوع دوم و $?$ نشان دهنده سوالی است که برای محمد پیش می‌آید. سپس دو عدد $l_i$ و $r_i$ ($1 \leq l_i \leq r_i \leq n$) آمده است که نشان‌ دهنده بازه‌ی مورد نظر است. اگر عملیات از نوع اول باشد، یک عدد $(-10^9 \leq x_i \leq 10^9)$ نیز در ادامه خط آمده است که نشان دهنده عددی است که باید بازه را با آن جمع کرد. دقت کنید که اندیس عضو اول آرایه یک است.

$1 \leq n \leq 3 \times 10^5$ $1 \leq q \leq 3 \times 10^5$ $-10^9 \leq a_i \leq 10^9$ $-10^9 \leq x_i \leq 10^9$ $1 \leq l_i \leq r_i \leq n$

خروجی🔗

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

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

مثال🔗

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

4 4
2 3 -1 -1
? 1 4
+ 3 3 4
\* 1 3
? 2 4

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

7
4

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

6 8
-2 7 3 4 1 6
? 1 6
+ 3 5 4
\* 1 6
+ 5 6 -3
? 2 5
\* 3 5
+ 4 4 -2
? 3 6

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

21
5
10