شرکت «بساز و بنداز» به تازگی پروژه‌ی رنگ‌آمیزی دیوار‌ بزرگ شهر را انجام داده‌است و آقای مهندس در حال جمع‌آوری داده‌های این پروژه است تا عملکرد شرکت خود را در این پروژه بسنجد. اگر دیوار بزرگ شهر را به صورت $n$ قسمت مساوی پشت‌سرهم در نظر بگیریم، یک داده به صورت $t\ l\ r\ c$ به این معنی است که در زمان t، رنگ قسمت‌های $l$ام تا $r$ام دیوار با رنگ $c$، رنگ‌آمیزی می‌شود. در حین جمع‌آوری داده‌ها سوال‌هایی به این شکل برای آقای مهندس پیش می‌آید: «دیوار $i$ام در زمان $t$ به چه رنگی بوده است؟» دقت کنید که آقای مهندس داده‌ها را بر حسب زمان‌شان جمع‌آوری نمی‌کند. یعنی امکان دارد داده‌ها بر حسب زمان مرتب نباشند و آقای مهندس سوال‌ها را با توجه به داده‌هایی که تا قبل از پیش‌آمدن این سوال جمع‌آوری کرده، پاسخ می‌دهد.

حال شما باید برنامه‌ای بنویسید که با گرفتن داده‌های مربوط به رنگ‌آمیزی و سوال‌های آقای مهندس، پاسخ سوال‌های آقای مهندس را در خروجی چاپ کند.

رنگ همه‌ی قسمت‌های دیوار در ابتدای کار $0$ است. بنابراین اگر با داده‌های جمع‌آوری شده رنگ خانه‌ی سوال پرسیده‌شده معلوم نشود، پاسخ سوال $0$ است.

• در سطر اول ورودی دو عدد طبیعی $n$، تعداد قسمت‌های دیوار، و $q$، تعداد داده‌ها و پرسش‌ها، آمده است. در هر کدام از $q$ سطر بعدی، یا یک داده در مورد رنگ‌آمیزی دیوار و یا یک پرسش آمده است.
• داده رنگ‌آمیزی: «$t\ l\ r\ c$ ~»: دیوار $l$ام تا $r$ام دیوار در زمان $t$ به رنگ $c$، رنگ‌آمیزی می‌شود.
• پرسش:‌ «$t\ x$ ?»: دیوار $x$ام در زمان $t$ با استفاده از اطلاعات کنونی، به چه رنگی است؟
• تمامی زمان‌هایی که در ورودی آمده است متمایزند.
• $2 \leq n, q \leq 10^5$
• $1 \leq l \leq r \leq n$
• تمامی اعداد ورودی بین $1$ تا $10^9$ هستند.

سطر $i$ام خروجی پاسخ پرسش $i$ام آقای مهندس است.

• زیرمسئله اول (۵ نمره): $n, q \leq 5000$
• زیرمسئله دوم (۱۰ نمره): $q \leq 5000$
• زیرمسئله سوم (۱۵ نمره): طول بازه‌ها حداکثر $50$ است. یعنی برای تمام داده‌ها $r − l \leq 50$
• زیرمسئله چهارم (۲۰ نمره): $n \leq 10000$
• زیرمسئله پنجم (۵۰ نمره): بدون محدودیت اضافی

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

• سوال قبل