The Queen Mother hosted a peach banquet and invited all immortals to attend. Her drawed up the list and hand it over to Taishang Laojun. When the Laojun looked at the list, he found that there were N Immortals (numbered 1 to N respectively), but there was no Sun Wukong. In order to dispel Sun Wukong's doubts, he invited Sun Wukong. Sun Wukong was very happy to receive the invitation and came early. Before the party started, the restless Sun Wukong wandered around.

       When the banquet opened, the Sun Wukong didn't come back. The Laojun couldn't find the Sun Wukong for the moment, so he had to operate the banquet according to the list. In order to enliven the atmosphere, the Queen Mother announced that the banquet would be held by playing games. The rules of the game are as follows:

1、 Throw Q times of dice to form Q instructions, and each instruction corresponds to one action;

2、 Each time the Dicer is thrown, an integer game tag m and the immortal number range [a, b] affected by this instruction will be generated.

3、 If the tag m is a positive integer, each person in the interval [a, b] would be sended m peaches to his hand;

4、 If the tag m is 0, find the sum of the number of peaches in each person's hand in the interval [a, b];

       Sun Wukong had eaten the elixir in the alchemy furnace of Taishang Laojun and the peaches in the Pantaoyuan. He had nothing to do, and suddenly remembered about the peach banquet, he hid on the beams of the banquet hall to watch the excitement. At this time, the Queen Mother was just announcing the rules of the game for the banquet, and was about to let the Taishang Laojun start the game according to the list of banquets. After hearing the rules of the game, Sun Wukong found that his name was not on the banquet list. He was unhappy and determined to cast a spell to make a prank. A prank casts a spell when m is 0 in the game rules, and the result of the spell will affect the execution of other instructions.

       Sun Wukong is a loner and likes odd numbers. His spells are: if both a and b in the interval [a, b] are odd, the meaning of this instruction would be changed. The new meaning is: the peach in each person's hand in the numbered interval [a, b] will be taken away by Sun Wukong, that is, the number of peaches in the hands of these immortals will be cleared.

       So, after Sun Wukong cast his magic, how did the game go on?

The first line contains two positive integers N and Q (1 ≤ N, Q ≤ 100000), respectively indicating that there are N immortals on the list and Q instructions in the game.

Next, there are Q lines, each corresponding to an instruction. Each instruction is three integers m (0 ≤ m ≤ 10000), a and b (1 ≤ a ≤ b ≤ N), respectively representing the game tag m and the immortal number interval [a, b] affected by this instruction.

Output each instruction that needs to be output in order, as an integer, that is, the sum of the number of peaches in the hands of each immortal in the interval [a, b].