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

---

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

پس از بحث‌ها و مشاجرات فراوان، تصمیم گرفتند تا برای دادرسی به سراغ شخص ثالث بروند.

شخص ثالث عقیده دارد نتیجه نگرفتن تقصیر کسی است که در بازی نیم ضعیف‌تر باشد، بازی نیم، بازی است که با \(n\) کیسه تیله انجام می‌شود. همانطور که می‌دانید برنده شدن در بازی نیم بستگی به \(xor\) تعداد تیله‌های همه کیسه‌ها با هم دارد.

در ابتدا \(n\) کیسه خالی وجود دارد. میلاد می‌خواهد طوری کیسه‌ها را پر کند که حتما برنده بازی باشد.

میلاد در هر مرحله می‌تواند دو عدد \(l\) و \(r\) انتخاب کند به طوری که \( 1 \le l \le r \le n\) و به تمام کیسه‌های بین \(l\) و \(r\) (شامل ابتدا و انتهای‌ بازه) یک تیله اضافه کند.

میلاد کار خودش را بلد است و تنها کمکی که از شما می‌خواهد این است که پس از هر مرحله که میلاد انجام می‌دهد، \(xor\) تعداد تیله‌های تمام کیسه‌ها را به او بگویید.

ورودی

در خط اول ابتدا \(n\) که تعداد کیسه‌هاست و سپس \(q\) که تعداد مراحل پر کردن است به شما داده می‌شود.

سپس در \(q\) خط بعدی، در هر خط دو عدد \(l_i\) و \(r_i\) داده می‌شود که ابتدا و انتهای بازه‌ای است که در مرحله \(i\)-ام توسط میلاد تغییر می‌کند.

\[ 1 \le n , q \le 100\ 000\] \[ 1 \le l_i \le r_i \le n\]

خروجی

در \(q\) خط، در خط \(i\) ام، \(xor\) تعداد تیله‌های تمام کیسه‌ها پس از انجام مرحله \(i\) ام را چاپ کنید.

مثال

ورودی نمونه

5 4
1 5
3 5
5 5
1 5

خروجی نمونه

1
2
3
4