دانشمندان نجوم و اخترفیزیک به روابط عجیبی بین کهکشان‌ها پی برده‌اند. آن‌ها $n$ کهکشان پیدا کرده‌اند که هر کدام متشکل از $2^m$ ستاره با شماره‌های 0 تا $2^m-1$ هستند. طبق مشاهده‌ی دانشمندان هرازگاهی بین دو کهکشان پدیده‌ی «پیوندسازی شیری» با یک سه‌تایی $(x,y,p)$ قابل نمایش است. یک پیوندسازی شیری با مشخصه‌ی $(x,y,p)$ به این معنا است که بین کهکشان‌های $x$ و $y$ و به ازای هر $i$ و $j$ که $i\oplus j$ برابر $p$ است ($\oplus$ نماد عملگر $xor$ است) یک راه شیری بین ستاره‌ی شماره‌ی $i$ از کهکشان $x$ و ستاره ی شماره‌ی $j$ از کهکشان $y$ ایجاد می‌شود. پیوندسازی هم تنها بین کهکشان‌های مختلف روی می‌دهد و یک کهکشان مختلف روی می‌دهد و یک کهکشان نمی‌تواند با خودش پیوندسازی شیری انجام دهد. دقت کنید که راه شیری کهکشان نیست بلکه یک «مسیر بین کهکشانی» است.

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

• $1xyp$: رخ دادن یک پیوندسازی شیری با پارامترهای $(x,y,p)$
• $2xy$: اندازه‌ی مولفه‌ی همبندی ستاره‌ی شماره‌ی $y$ از کهکشان $x$ چقدر است؟
• $3$: تعداد کل مولفه‌های همبندی چند تاست؟

سطر اول ورودی شامل سه عدد طبیعی $n$، تعداد کهکشان‌ها، $m$ و $q$، تعداد پرسش‌ها، آمده است.($1\leq n \leq 10^5$، $0\leq m \leq 40$ و $1\leq q \leq 4\times 10^5$)

در هر یک از $q$ سطر بعدی یکی از درخواست‌ها با فرمتی که در صورت سوال ظاهر شده قرار دارد.

خروجی باید شامل پاسخ به درخواست‌های نوع ۲ و ۳ بر حسب زمان پرسیده شدنشان باشد.

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

• سوال بعد
• سوال قبل