Bitmasks are cool. A bitmask is a string of binary bits (0s and 1s). For example: “01010” is a bitmask. Kuldeep is a naughty but brilliant computer scientist. In his free time, he writes some random programs to play with bitmasks. He has a PhD student under him and to test him (and entertain himself), he has given him the following task: Given a number N, write a bitmask of length N containing all 0s. Now, you are given Q operations. Each operation contains two numbers (l, r) as input. An operation can be one of the following:
Update operation: Take the XOR of all the bits in the bitmask from index l to r (both inclusive) with 1.
Query operation: Count the number of set bits in the bitmask between index l to r (both inclusive).You need to find the sum of all the queries. Note:
- In case there are no queries, return 0.
- As the answer can be large, output the answer mod 1000000007
- Consider 0 based indexing
Constraints:
1 <= N <= 100000
1 <= Q <= 100000
0 <= l, r < N
Input format:
int A: Number N as described above
vector<vector > B: Q operations as described above.
Each row contains three numbers (type, l, r). If type is 0, its an update operation else a query operation.
Example:
Input:
N = 5
Operations: [[0, 1, 3], [1, 1, 2], [0, 0, 4], [1, 3, 4]]
Output:
3
Explanation:
Initial mask: 00000
Operation 1: Update (1,3) , Resulting mask = 01110
Operation 2: Query (1,2), Answer to query = 2
Operation 3: Update (0, 4), Resulting mask = 00001
Operation 4: Query (3,4), Answer to query = 1
Sum of all the queries = 2+1 = 3
Answer = 3%1000000007 = 3
You need to find the sum of all the queries.