====== Galaxy ====== دانشمندان نجوم و اخترفیزیک به روابط عجیبی بین کهکشان‌ها پی برده‌اند. آن‌ها $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$ سطر بعدی یکی از درخواست‌ها با فرمتی که در صورت سوال ظاهر شده قرار دارد. ===== خروجی ===== خروجی باید شامل پاسخ به درخواست‌های نوع ۲ و ۳ بر حسب زمان پرسیده شدنشان باشد. ===== محدودیت‌ها ===== * محدودیت زمان: ۲ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |3 1 10 \\ 3 \\ 1 1 2 0 \\ 3 \\ 2 1 0 \\ 1 2 3 1 \\ 3 \\ 2 3 1 \\ 1 1 3 0 \\ 3 \\ 2 2 1 | 6 \\ 4 \\ 2 \\ 2 \\ 3 \\ 1 \\ 6| * [[سوال ۳|سوال بعد]] * [[سوال ۱|سوال قبل]]