Design a thread-safe fixed-window rate limiter. Each client may make at most limit allowed requests during one window.

The constructor receives a clock function that returns the current logical time in milliseconds. The judge controls this clock, so you should not read the system clock or create timer threads.

Windows are globally aligned. The current window is:

For example, with windowMillis = 10, times 0 through 9 belong to window 0, times 10 through 19 belong to window 1, and so on.

Implement allow(clientId). It returns true and consumes one permit when that client has used fewer than limit permits in the current window. Otherwise, it returns false. Every client has an independent counter.

Calls to allow may happen concurrently on the same limiter. The window lookup, optional reset, limit check, and increment must form one atomic operation.

The judge creates the limiter, supplies the clock, and starts all worker threads. Your implementation should contain only the rate-limiter state and synchronization.

The judge also preloads the standard concurrency, callback, and collection APIs for each supported language. You do not need to add import, include, or using statements.

Example 1:

Input:

Output:

Explanation: Client 7 consumes both permits in window 0. Time 10 begins window 1, so its counter resets.

Example 2:

Input:

Output:

Explanation: Each client receives its own permit. Requests from client 1 do not consume client 2's capacity.

Constraints