Нулі та одиниці

Їжачок Аліна, переглядаючи свої старі зошити знайшла в одному з них неймовірно цікавий масив з нулів. Виявилось, що Аліна з цим масивом вміє робити кілька неймовірно цікавих операцій:

• Присвоїти елементу в позиції x значення 1.

• Присвоїти елементу в позиції x значення 0.

• Замінити на відрізку від l до r всі нулі на одиниці і навпаки.

• Повернути масив в стан, який був після x-ої операції.

• Знайти кількість одиниць на підвідрізку масиву від l до r.

Input

В першому рядку задано два натуральні числа N ≤ 10^5 i M ≤ 2 ∙ 10^5, що позначають розмір масива і кількість операцій відповідно. В наступних M рядках задано інформацію про операції.

Output

Для кожної операції типу 5 вивести кількість одиниць на підвідрізку від l до r.

Examples