Code School of Analytics
IntermediateSimulation & Finance25 points

Throttle the noisy API clients

A public weather API in Singapore protects itself with a sliding-window rate limit. Each client may have at most M allowed requests in any window of W seconds. A request arriving at second t is allowed when the client has fewer than M allowed requests whose times s satisfy t - W < s <= t (so a request exactly W seconds old no longer counts). Blocked requests are not counted against the client later.

Timestamps are given as HH:MM:SS strings within a single day and the requests arrive in chronological order (several may share the same second). Each client is counted separately.

Task: lines 1 to 3 hold M, W and N. Then N lines of the form HH:MM:SS client. For every request print HH:MM:SS client ALLOWED or HH:MM:SS client BLOCKED, in input order. Finish with a last line Blocked total: K.

Sample tests

Input

3
10
8
12:00:00 alice
12:00:01 alice
12:00:01 bob
12:00:05 alice
12:00:09 alice
12:00:10 alice
12:00:11 alice
12:00:11 bob

Expected output

12:00:00 alice ALLOWED
12:00:01 alice ALLOWED
12:00:01 bob ALLOWED
12:00:05 alice ALLOWED
12:00:09 alice BLOCKED
12:00:10 alice ALLOWED
12:00:11 alice ALLOWED
12:00:11 bob ALLOWED
Blocked total: 1

Input

1
5
4
09:00:00 x
09:00:04 x
09:00:05 x
09:00:09 x

Expected output

09:00:00 x ALLOWED
09:00:04 x BLOCKED
09:00:05 x ALLOWED
09:00:09 x BLOCKED
Blocked total: 2

Your answer is also checked against 3 hidden tests.