Mitch Jones is fighting in the WoW 3v3 Arena! There are ~N~ different abilities, numbered ~1, 2, \dots, N~. In order for the next ability that Mitch uses on the target ~T~ to be effective, the ability must have been cast less than ~K~ times beforehand, otherwise the ability will not be cast successfully. Mitch will cast ~J~ spells, each of which adds ~I~ casts to each ability in the range ~X_i, X_{i+1}, \dots, X_f~ for the specific target ~T~. All abilities start with ~0~ casts.

Given all of the abilities Mitch casts, determine the number of abilities on each target that he will be able to cast successfully.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10^5)~, the number of different abilities.

The second line will contain the integer ~K~ ~(1 \le K \le 10^4)~, the number of casts that render an ability ineffective.

The third line will contain the integer ~J~ ~(1 \le J \le 10^5)~, the number of spells that Mitch casts.

The next ~J~ lines will contain 4 space-separated integers.

These integers will be in the order: ~X_i, X_f, I, T~:

~(1 \le X_i \le X_f \le N)~, the range of abilities that are cast from the ~J^\text{th}~ spell.

~(1 \le I \le 10^9)~, the number of times the above-mentioned abilities are cast.

~(1 \le T \le 3)~, the target that the ~J^\text{th}~ cast is used on.

Output Specification

Output ~3~ lines: on the ~i^\text{th}~ line, output the number of abilities that Mitch will be able to successfully cast on the ~i^\text{th}~ target.

Sample Input

5
3
6
3 4 4 3
1 5 3 1
1 1 9 3
1 3 4 3
3 5 8 1
1 4 3 3

Sample Output

0
5
1

Sample Explanation

There are 5 different types of abilities, and each ability has a maximum counter value of 3. There are 6 abilities that are cast. The first one is used on target 3, adding 4 to the counter of spells 3 and 4 on that target. The second spell is used on target 1, adding 3 to the counter of spells 1 to 5, and so on. In the end, out of the 5 spells, for target 1, all spells have a counter greater than 3 and therefore, 0 spells can be cast, for target two, since no spells were cast, all 5 spells can be cast successfully, and for target 3, 1 spell has a counter less than 6.