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

یک دنباله به طول $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

درخواست اول از نوع یک است که در بازه ۳ تا ۵ تمام اعداد ۲ را به ۳ تبدیل میکند.

درخواست دوم چهارمین عدد در حالت مرتب شده ی بازه ۱ تا ۵ را میخواهد. اعداد بازه ۱ تا ۵ به ترتیب ۱ ۲ ۳ ۳ ۷ اند.

درخواست سوم اعداد بازی ۱ تا ۵ که برابر با ۷ اند را به ۲ تغییر میدهد.

و در نهایت درخواست آخر سومین عدد در حالت مرتب شده در بازه ۴ تا ۷ را میخواهد که اعداد این بازه ۲ ۳ ۴ ۴ اند.

ارسال پاسخ برای این سؤال