Sliding Window Rate Limiter

Sliding Window Rate Limiter Implement a per-client sliding-window rate limiter. You are given a window length window_ms in milliseconds and a maximum number of requests limit allowed for each client in a window. For each request (timestamp_ms, client_id): Allow it and output ALLOW if the number of previously allowed requests for that client in (timestamp_ms - window_ms, timestamp_ms] is smaller than limit. Otherwise reject it and output REJECT. Rejected requests must not count toward the request total. Timestamps are nondecreasing in the input. Requests from different clients must be rate-limited independently. Input Format The first line contains three integers: window_ms limit n where: window_ms: window length, 1 <= window_ms <= 10^9 limit: maximum allowed requests per client per window, 1 <= limit <= 10^6 n: number of requests, 1 <= n <= 10^6 The next n lines contain: timestamp_ms client_id 0 <= timestamp_ms <= 10^18 client_id is a string without spaces. Output Format Output ALLOW or REJECT for every request. Example Input: 1000 2 5 0 alice 100 alice 999 alice 1000 alice 1001 alice Under the strict interval rule (t - window_ms, t], the request at timestamp 0 has expired by timestamp 1000. Implement the stated boundary rule consistently. Example Input 1000 2 5 0 alice 100 alice 999 alice 1000 alice 1001 alice Output ALLOW ALLOW REJECT ALLOW REJECT