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

---

علی کوچولو، به تازگی علاقه‌ی زیادی به چراغ‌ها پیدا کرده است. به همین دلیل او \(n\)‌رشته چراغ، هر یک شامل \(10^9\) چراغ خریده است و رشته‌ها را با شماره‌های 1 تا \(n\) شماره‌گذاری کرده است تا با آن‌ها بازی کند. امروز او تصمیم گرفته بازی زیر را با پدرش انجام دهد. در هر مرحله از بازی علی یکی از کارهای زیر را انجام می دهد:

1. سه عدد\(a\) و \(b\) که \(1 \leq a,b \leq n\) و \(x\)‌ که \(1 \leq x \leq 10^9 \) را انتخاب می کند و چراغ \(x\) ام هریک از رشته‌های \(a\)ام تا \(b\)ام (شامل هر دو) را روشن می کند. اگر چراغ \(x\)ام یک یا چندتا از این رشته‌ها روشن باشد، وضعیت این چراغ در آن رشته‌ها تغییر نمی‌کند.

2. سه عدد\(a\) و \(b\) که \(1 \leq a,b \leq n\) و \(x\)‌ که \(1 \leq x \leq 10^9 \) را انتخاب می کند و چراغ \(x\) ام هریک از رشته‌های \(a\)ام تا \(b\)ام (شامل هر دو) را خاموش می کند. اگر چراغ \(x\)ام یک یا چندتا از این رشته‌ها خاموش باشد، وضعیت این چراغ در آن رشته‌ها تغییر نمی‌کند.

3. دو عدد\(a\) و \(b\) که \(1 \leq a,b \leq n\) را انتخاب می کند و از پدرش تعداد کل لامپ‌های روشن رشته‌های \(a\)ام تا \(b\)ام (شامل هر دو) را می‌پرسد.

پدر علی بسیار درگیر است ولی نمی‌خواهد پسرش را ناراحت کند. درنتیجه از شما خواسته‌است که برنامه‌ای بنویسید که به سوال‌های علی پاسخ دهد. لازم به ذکر است که پیش از شروع بازی، علی تمام چراغ‌ها را خاموش می‌کند.

ورودی

درخط اول ورودی، دو عدد \(n\) و \(q\) که به ترتیب تعداد رشته‌های چراغ و تعداد مراحل بازی هستند آمده‌اند. در هر یک از \(q\) خط بعدی، توضیحات یک مرحله از بازی آمده است. در هر یک از این \(q\) خط ابتدا نوع عملیات با یکی از حروف +،- یا ? مشخص شده است که به ترتیب متناظر با عملیات‌های اول، دوم و سوم گفته شده در صورت سوال هستند. سپس اعداد مربوط به آن عملیات به همان ترتیب گفته شده در سورت سوال آمده‌اند. یعنی هر یک از این \(q\) خط به یکی از سه شک زیر هستند:

1. + a b x

2. - a b x

3. ? a b

\[1 \leq n \leq 10^9\] \[1 \leq q \leq 500\ 000\] \[1 \leq a \leq b \leq n\] \[1 \leq x \leq 10^9\]

خروجی

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

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۱۳	\( q \le 1\ 000\)
۲	۱۸	\( x = 1\)
۳	۴۳	\( x,n,q \le 100\ 000\)
۴	۲۶	بدون محدودیت اضافی

مثال

ورودی نمونه

5 11
+ 3 4 2
? 1 3
+ 1 5 2
? 1 3
- 3 3 1
? 1 3
+ 3 3 1
? 4 5
? 1 3
- 1 5 1
? 1 2

خروجی نمونه

1
3
3
2
4
2