Switches

Time limit1sMemory limit128 MB

Summary
Given a switch array of size N, support range flips and range count-of-on queries over M operations, best solved with a segment tree with lazy propagation.
Level

Medium5 of 10

Topics
Segment tree, Intervals, Implementation
Solved
No attempts yet

Problem

There are N switches numbered from 1 to N in Jungyu's house. Initially, every switch is off.

You must process two kinds of operations.

  • 0 S_i T_i: flip every switch from switch S_i through switch T_i. An on switch becomes off, and an off switch becomes on.
  • 1 S_i T_i: count how many switches are currently on from switch S_i through switch T_i.

Process all operations in the order they are given.

Input

The first line contains the number of switches N (2 ≤ N ≤ 100,000) and the number of operations M (1 ≤ M ≤ 100,000).

Each of the next M lines contains three integers O, S_i, and T_i describing one operation. If O is 0, flip the state of every switch in the range. If O is 1, answer how many switches are on in the range.

Output

For each operation with O = 1, print the number of switches that are on in the requested range, one answer per line.

Examples1

  1. Example 1

    Input
    4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
    Expected output
    1
2