Sliding-Window Rate Limiter III

Problem: Implement a Sliding Window Rate Limiter

Create a rate limiter that evaluates requests separately for each user.

You receive:

• limit: the greatest number of requests one user may have accepted during a window;
• window: the window duration, measured in seconds;
• a sequence of requests, with each request specifying:
  • timestamp: when the request arrives, in seconds;
  • user_id: the user making the request.

Report whether every request is accepted or denied.

Rules:

• At time t, count only requests for that user that were previously accepted and whose timestamps fall within [t - window + 1, t];
• Accept the current request and save its timestamp when that count is below limit;
• Reject the request without saving it when the count has reached limit;
• Each user has an independent rate limit;
• The request timestamps appear in non-decreasing order.

Input Format

The first input line provides three integers:

limit window q

Their meanings are:

• limit is the largest number of accepted requests in one window;
• window is the number of seconds covered by the window;
• q is the total number of requests to process.

Each of the following q lines contains:

timestamp user_id

Output Format

Write one result per request:

• true when the request passes the limiter;
• false when the request is denied.

Constraints

• 1 <= limit <= 10^5
• 1 <= window <= 10^9
• 1 <= q <= 2 * 10^5
• 0 <= timestamp <= 10^18
• user_id is a non-empty string with length at most 64
• Request timestamps are in non-decreasing order

Example

Input:

2 6 6
3 sam
4 sam
5 sam
6 lee
8 sam
10 sam

Output:

true
true
false
true
false
true

The first two requests from sam are accepted, the request at time 5 is denied because both earlier accepted requests remain in the window, lee is evaluated independently, the request at time 8 is still blocked by sam's accepted requests at 3 and 4, and by time 10 the request at time 3 has expired from the six-second window.