بچه‌ی آقا داوود همه‌ی $N$ مداد رنگی‌‌اش را بر حسب رنگشان مرتب کرده است. مداد رنگی‌ها از چپ به راست با اعداد $1$ تا $N$ نام‌گذاری شده‌اند. او در $M$ مرحله هر بار یکی از اعمال زیر را روی دنباله‌ی مداد رنگی‌هایش انجام می‌دهد:

• نوع اول: مداد رنگی $i$-ام تا $j$-ام (شامل این دو) را طبق ترتیب اولیه‌شان در جایشان بچین.
• نوع دوم:‌ مداد رنگی $i$-ام تا $j$-ام (شامل این دو) را برعکس ترتیب اولیه‌شان در جای‌شان بچین.

منظور از ترتیب اولیه در عملیات‌ها ترتیبی است که هیچ عملیاتی روی آن انجام نشده است.

پس از هر عملیات بچه‌ی آقا داوود از او می‌خواهد تا میزان به هم ریختگی ترتیب فعلی مداد رنگی‌ها را به او بگوید. می‌دانیم به‌هم‌ریختگی یک دنباله از مداد رنگی‌ها برابر با تعداد جفت مداد رنگی‌هایی است که عکس ترتیب اولبه‌شان در دنباله ظاهر شده‌اند. به عبارتی دیگر شما باید به آقا داوود کمک کنید تا تعداد نابجایی‌های دنباله‌ی مداد رنگی‌ها را در هر لحظه چاپ کند. آقا داوود پس از کمی بازی با بچه‌اش فهمیده‌است که هر دو بازه‌ای که بچه‌اش بر روی آن‌ها عملیات انجام می‌دهد گوگولی هستند. دو بازه گوگولی هستند اگر یا با هم اشتراک نداشته باشند یا یکی درون دیگری باشد. به عبارتی دیگر به ازای هر دو بازه‌ی $[a,b]$ و $[c,d]$ در ورودی دست کم یکی از عبارات زیر برقرار است:

• $a \leq b \leq c \leq d$ (اولی قبل دومی)
• $c \leq d \leq a \leq b$ (دومی قبل اولی)
• $a \leq c \leq d \leq b$ (دومی درون اولی)
• $c \leq a \leq b \leq d$ (اولی درون دومی)

• سطر اول ورودی شامل دو عدد طبیعی، $2 \leq N \leq 10^6$، تعداد مداد رنگی‌ها، و $1 \leq M \leq 2*10^5$، تعداد اعمال، است.
• سطرهای دوم تا $M+1$-ام هر کدام شامل دو عدد طبیعی، $1 \leq L \leq R \leq N$، شروع و پایان بازه آمده است. بعد از این دو یک حرف از {<, >} آمده است. حرف < به معنای عملیات نوع اول و حرف > به معنای عملیات نوع دوم است.
• در ۳۰ درصد از ورودی ها، $1 \leq M, N \leq 2000$، است.

خروجی شامل $M$ سطر است که سطر $i$-ام به هم ریختگی مدادرنگی ها بعد از عملیات $i$-ام است.

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