Problem G. Ganking

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Popular on-line game "Attack Of The Moderns 3" is played by two teams of 5 players each. During the match, players run around the map and try to kill members of opposing team by attacking them with various weapons and magic spells. Killed players respawn after a certain period of time.

Players of the first team are numbered from 1 to 5, players of the second team are numbered from 6 to 10. All attacks are recorded by the game for statistics gathering. Each attack is described by values t, a, v, k, where t is a time in seconds since the game start, a — the number of the attacking player, v — the number of the player being attacked, k = 1 if this attack killed the victim and 0 otherwise.

Gank is an event when one or more players attack and kill a single opponent while his teammates are elsewhere and unable to help. Specifically: let G be a set of players who attacked the victim during the last T seconds of the game before the kill. A kill is counted as a gank, if in that period of time:

All the players from the set G who attacked the victim of the gank are considered the participants of this gank.

Your program must, given the value of T and a sequence of N attack descriptions, count the number of ganks each player has participated in.

Input file format

Input file contains integers N T followed by N quartets of integers ti ai vi k.

Output file format

Output file must contain 10 integers — the numbers of ganks for each player.

Constraints

1 ≤ N ≤ 10000, 1 ≤ ti ≤ ti + 1 ≤ 105, 1 ≤ T ≤ 105. Either 1 ≤ ai ≤ 5 < vi ≤ 10 or 1 ≤ vi ≤ 5 < ai ≤ 10. Time between sequential kills of the same victim is greater than T.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
7 4
1 1 6 0
2 2 6 0
5 3 6 1
10 7 1 1
10 7 2 1
20 8 1 1
20 3 7 1
0 1 2 0 0 0 0 1 0 0 

0.061s 0.008s 13