D. Drums (1000 points)

Bertie decides that his motorbike gang needs a theme song. He is a novice drummer and he has composed a lot of songs during the long hours he spent wandering on the highway. He always had his pocket sound recorder and a small portable drum kit with him and by now he has countless hours of recordings accumulated. He needs your help to transcribe the grooves.

Input format

Each input is a wav file containing a recording of a session. Separate wav files of each kind of drum are also provided to make it possible to associate IDs with individual drums in his kit.
   drum sticks
source:
http://www.public-domain-image.com/cache/objects-public-domain-
images-pictures/drumsticks-laid-scross-drum_w725_h544.jpg
drumID sample
1 1_kick.wav
2 2_snare.wav
3 3_hihat.wav
4 4_hihat.wav
5 5_crash.wav
6 5_kettle.wav
7 5_cowbell.wav
8 8_triangle.wav
Source: http://www.drumsamples.org

NOTE: because <insert your favorite excuse here>, we accept both 3 and 4 for hihat, you don't need to distinguish between them.

For Drums, you will get only 5 inputs at the beginning of the contest. You will receive further inputs during the contest.

Output format

Output is a list of events, one event per line. An event consists an integer time stamp (miliseconds elapsed since the beginning of the recording), a space and an integer drumID. Events should be generated for each and every stroke and are accepted only if the drumID matches and time stamp is within +-20 ms. Output must be sorted by time stamp in increasing order. In case there are multiple events for the same time stamp, they should be ordered by drumID (lower ID comes first). Since Bertie has 4 limbs to play with, he can strike at most 4 instruments in the same moment. However, some cymbals may emit a long enough sound to overlap more than 4 other events.

Example

A valid solution for in0.wav (provided with the real inputs):
0 1
0 3
444 2
444 4
666 2
888 1
888 4
1110 2
1332 2
1332 4
1776 1
1776 5
2220 4
2220 6
2442 6
2664 1
2664 4
2886 7
3108 4
3108 7
3552 1
3552 3
3996 2
3996 8
4218 2
4440 1
4440 8
4662 2
4662 8
4884 2
4884 8