Mitch Jones is fighting in the WoW 3v3 Arena! There are ~N~ different abilities, numbered from ~(1,2,\dots,N-1,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~ waves of abilities, each of which adds ~I~ casts to each ability in the range ~(X_i,X_{i+1},\dots,X_{f-1},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 enemy 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 abilities 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 abilities that are cast on the ~J^\text{th}~ series of spells.

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

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

Output Specification

Output ~T~ lines, the number of crowd control types that would be successful when used on each 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.