Zeros and Ones

Hedgehog Alina discovered an intriguing array of zeros while going through her old notebooks. She realized she could perform several fascinating operations on this array:

• Set the element at position x to 1.

• Set the element at position x to 0.

• Swap all zeros to ones and all ones to zeros in the segment from l to r.

• Revert the array to the state it was in after the x-th operation.

• Count the number of ones in the sub-segment of the array from l to r.

Input

The first line contains two natural numbers N ≤ 10^5 and M ≤ 2 ∙ 10^5, representing the size of the array and the number of operations, respectively. The following M lines describe the operations.

Output

For each operation of type 5, output the number of ones in the sub-segment from l to r.

Examples