URI Online Judge | 2857

SpeedWagon Flow

By Dâmi Henrique, Inatel BR Brazil

Timelimit: 1

Employees of the AHDCW (Association of Human Density Control in Wagons) are working to generate some statistics on how many people use trains as a means of transportation and how they choose which wagon to enter.

They noted, from time to time, how many people got into certain wagons. To generate satisfactory data, employees need to know at certain times how many different people are within two ranges of wagons.

They need your help and all they gave you was a spreadsheet with the number N of wagons (from 1 to N from left to right), and the M activities that occurred on the day. The activities can be type 1 or type 2:

1 X Y - Means that Y people got into the X wagon.
2 A B C D - It means that they want to know the number of different people in the wagons of the intervals [A, B] and [C, D].

Consider that initially all wagons are empty.

Follows an illustration of the wagons at one point:

UOJ_383_H.png

If there is an activity of type 2 with (A=2, B=4, C=3, D=5), the answer will be 8, since there are 8 distinct people in these two intervals.

Input

The first line contains two integers N and (1 ≤ N ≤ 105) and (1 ≤ M ≤ N).  Each of the next M ines will contain an activity of type "1 X Y"  (1 ≤ X ≤ N and 1 ≤ Y ≤ 100) or type 2 "2 A B C D" (1 ≤ A, B, C, D ≤ N and AB and CD), both described above.

Output

For each type 2 activity, display the total number of different people in the given intervals.

Sample Input Sample Output

5 9
1 2 3
1 3 1
1 5 8
2 2 3 3 5
1 1 2
2 2 3 1 5
2 1 2 4 5
1 2 5
2 2 2 4 4

12
14
13
8