+ محدودیت زمان: ۳ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
+ منبع: آزمون عملی دوره ۲۴ المپیاد کامپیوتر
----------
شرکت «بساز و بنداز» به تازگی پروژه‌ی رنگ‌آمیزی دیوار بزرگ شهر را انجام داده‌است و آقای مهندس در حال جمع‌آوری داده‌های این پروژه است تا عملکرد شرکت خود را در این پروژه بسنجد. اگر دیوار بزرگ شهر را به صورت $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$ با استفاده از اطلاعات کنونی، به چه رنگی است؟
تمامی زمان‌هایی که در ورودی آمده است متمایزند. تمامی اعداد ورودی بین 1 تا $10^{9}$ هستند.
$$2\le n,q \le 10^5$$
$$1\le l\le r\le n$$
# خروجی
سطر $i$-ام خروجی پاسخ پرسش $i$-ام آقای مهندس است.
# زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت
|:------------------:|:----------:|:------------------:|
| ۱ | ۵ | $ n,q \le 5\ 000 $ |
| ۲ | ۱۰ | $ q \le 5\ 000 $ |
| ۳ | ۱۵ | طول بازه‌ها حداکثر ۵۰ است. |
| ۴ | ۲۰ | $n \le 10\ 000$|
| ۵ | ۵۰ |بدون محدودیت اضافی |
# مثال
## ورودی نمونه
```
4 6
? 2 1
~ 1 1 3 1
? 3 1
~ 5 2 4 2
? 4 2
? 6 2
```
## خروجی نمونه
```
0
1
1
2
```
(۲۴امین دوره المپیاد کامپیوتر - آزمون دوم - ۱۳۹۳/۰۵/۳)