+ محدودیت زمان: ۸ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت + منبع: آزمون نهایی اول دوره ۲۷ المپیاد کامپیوتر ---------- زمان زیادی تا کانتست نمانده بود و آنیتا دیگر حوصله نداشت برای سوالات داستان بسازد، برای همین او از شما می‌خواهد که سوال زیر را حل کنید. یک دنباله به طول $n$ از اعداد $1$ تا $n$ داده شده است و هر بار یکی از دو نوع درخواست زیر داده می‌شود: نوع اول: یک بازه از دنباله و دو عدد $x$ و $y$ داده می‌شود و تمام عنصرهای $x$ آن بازه به $y$ تبدیل می‌شوند. نوع دوم :‌ یک بازه از دنباله و یک عدد $k$ داده می‌شود و می‌پرسد «اگر تمام بازه را از کوچک به بزرگ مرتب کنیم، عنصر $k$ام کدام است؟». # ورودی در خط اول ورودی دو عدد $n$، تعداد اعداد دنباله و $m$، تعداد درخواست‌ها، آمده‌است. در خط دوم $n$ عدد آمده است که عدد $i$ام، $a_i$، عدد $i$ام دنباله را نشان می‌دهد. در $m$ خط بعدی، در هر خط یک درخواست به یکی از دو شکل زیر آمده‌است: هر عدد $x$ در بازه $l$ تا $r$ از دنباله (شامل خود آن‌ها) به $y$ تبدیل می‌شود. اگر بازه $l$ تا $r$ از دنباله (شامل خود آن‌ها) را از کوچک به بزرگ مرتب کنیم، $k$امین عنصر آن را چاپ کنید. $$1 \le n, m \le 100\ 000$$ $$1 \le a_i \le n$$ $$1 \le l \le r \le n$$ $$1 \le x, y \le n$$ $$1 \le k \le r - l + 1$$ # خروجی به ازای هر درخواست نوع دوم عدد خواسته‌ شده را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱ | ۹ | $1 \le n, m \le 1\ 000$ | |۲| ۲۳ | همه درخواست ها از نوع دوم هستند | |۳| ۶۸ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 7 4 1 2 2 7 3 4 4 1 3 5 2 3 2 1 5 4 1 1 5 7 2 2 4 7 3 ``` ## خروجی نمونه ۱ ``` 3 4 ``` درخواست اول از نوع یک است که در بازه ۳ تا ۵ تمام اعداد ۲ را به ۳ تبدیل میکند. درخواست دوم چهارمین عدد در حالت مرتب شده ی بازه ۱ تا ۵ را میخواهد. اعداد بازه ۱ تا ۵ به ترتیب ۱ ۲ ۳ ۳ ۷ اند. درخواست سوم اعداد بازی ۱ تا ۵ که برابر با ۷ اند را به ۲ تغییر میدهد. و در نهایت درخواست آخر سومین عدد در حالت مرتب شده در بازه ۴ تا ۷ را میخواهد که اعداد این بازه ۲ ۳ ۴ ۴ اند.