Allow or Deny: A Sliding-Window Rate Limiter

An API allows each user at most limit requests in any window of W milliseconds. Requests arrive in time order; for each one, print ALLOW or DENY.

A request by user u at time t is allowed if fewer than limit of u's allowed requests happened at times s with t - W < s <= t. Denied requests don't count toward anyone's limit - so a request leaves the window exactly W milliseconds after it was made.

Implement Solution(int limit, long windowMillis) and boolean allow(String user, long time).

In Python: Solution(limit, window_millis) and allow(user, time) returning a bool; collections.deque is the queue.

Input: limit and W; the number of requests n; then n lines of time user, with non-decreasing times.

Example

Input:
2 1000
5
0 ana
10 ana
20 ana
999 ana
1000 ana

Output:
ALLOW
ALLOW
DENY
DENY
ALLOW

Ana's requests at 0 and 10 use up her limit. At 20 and 999 both are still inside the window. At 1000 the request from time 0 has left (1000 - 1000 < 0 is false), so one slot is free.

• 1 <= limit <= 10^5; 1 <= W <= 10^12
• 1 <= n <= 2 * 10^5; 0 <= time <= 10^12, non-decreasing
• users are 1-10 letters and digits