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

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

سپس پیرمرد کمی فکر می‌کند و می‌گوید: «عه ببخشید یه شرطش رو یادم رفت بگم.» شرط اضافه‌ی پیرمرد این بود که مجموع اعداد فرزندان هر راس، نباید از عدد برچسب خود آن راس بیشتر بشود. مثلا اگر از یک راس برچسب $3$ آویزان باشد و آن راس ۲ فرزند داشته باشد که به یکی از آن‌ها برچسب $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$.

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

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

• زیرمسئله اول (۱۱ نمره): $q=0$
• زیرمسئله دوم (۱۱ نمره):$n, q \le 3000$
• زیرمسئله سوم (۲۹ نمره):برچسب‌ها حذف نمی‌شوند
• زیرمسئله چهارم (۲۳ نمره): ارتفاع درخت از $\sqrt{n}$ کمتر است
• زیرمسئله چهارم (۲۶ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $1 \le r \le 3 \times 10^5$
• $1 \le n \le 2 \times 10^5$
• $0 \le q \le 2 \times 10^5$
• $1 \le u, v \le n$
• سوال نوع اول: $2 \le u \le n$و $0 \le v \le r$
• سوال نوع دوم: $2 \le u \le n$
• تضمین می‌شود که عملیات نوع اول روی رئوسی که برچسب ندارند انجام شود و عملیات نوع دوم روی رئوسی که برچسب دارند.

• سوال قبل