Pokeface

题目描述

魔术师将一叠扑克顺次在桌上排成一行，初始全部正面朝上。随后，他每次挥一挥衣袖，都会翻转一连串的扑克，改变它们的正反朝向。从古代传下来的规矩，魔术师皆有师傅，他们要随时准备回答师傅的问题。问题形如：目前从第i张扑克牌到第j张扑克牌中，有几张正面朝上？



作为魔术师的助手，你被要求学习程序设计、算法与数据结构。现在，魔术师把这个问题交给了你，你需要编写一个程序，维护相应的数据结构来保存桌子上牌面的情况，同时对于师傅的每一个问题，你要用尽量快的速度计算出答案。



输入

第一行包含三个正整数n、p和q。n表示扑克牌的数量，p表示魔术师的挥一挥次数，q表示师傅的问话次数。



接下来共p+q行，每行包含一个操作，操作分为2种：



H i j 魔术师挥一挥，改变了第i张牌到第j张牌的正反

Q i j 师傅问话：截至目前，第i张到第j张牌中有多少张正面朝上

操作中恰好包含p次H操作，q次Q操作，与第一行的p和q吻合。H操作和Q操作的范围均包含边界（即第i张和第j张牌）。



对于每个操作，输入保证1 ≤ i ≤ j ≤ n。



输出

对于每次Q操作，输出一行，包含一个整数，表示问题的答案。

提示：线段树-Pokeface

Title Descr iption

The magician will stack poker table sequentially in a row, all the initial face-up. He then every wisp will flip a series of poker pros and cons of changing their orientation. The rules handed down　ancient times, the master magician Jie, they be ready to answer the teacher s questions. Question of the form: Currently playing cards　i to j-card poker, there are a few face-up?



As a magician s assistant, you are required to learn programming, algorithms and data structures. Now, the magician put this question to you, you need to write a program to maintain appropriate data structure to hold the cards on the table face the situation, while the master for each question, and you want to use as quickly calculate the answer.



Enter

The first line contains three positive integers n, p and q. n represents the number of poker, p represents the wave of the magic number, q represents the number of master s questioning.



Next, a total of p+ q rows, each containi