Implement a Work Queue with Leases, Retries, and a Dead-Letter Queue

Implement an in-memory work queue that supports reservation, completion, failure, lease timeouts, retries, and a dead-letter queue (DLQ). Implement the following operations: ADD now job_id max_retries: Add a job at time now. max_retries is the maximum number of retries allowed after the initial attempt. RESERVE now lease_duration: Select the available job that was enqueued earliest, reserve it for lease_duration time units, and return its job_id plus a unique lease token. Return NONE if no job is available. COMPLETE now job_id token: Mark a job completed only if it is currently leased and the token matches. Otherwise, ignore the operation. FAIL now job_id token: If the job is leased and the token matches, the current attempt fails. Re-enqueue it immediately if retries remain; otherwise move it to the DLQ. DLQ now: Print all job IDs currently in the DLQ in the order in which they entered it, or EMPTY if there are none. Timeout semantics Before every operation, process every lease with lease_until <= now: An expired lease counts as a failed attempt. If the retry budget remains, re-enqueue the job immediately. Otherwise, move the job to the DLQ. The initial reservation is not a retry. Therefore, a job may fail at most max_retries + 1 times in total. For example, when max_retries = 0, the first FAIL or lease timeout sends the job to the DLQ. Input format The first line contains the number of operations q. Each of the next q lines is one command above. Timestamps now are non-decreasing. job_id is a whitespace-free string, and no job is added twice. 0 <= q <= 2 * 10^5. 0 <= now, lease_duration <= 10^9. Output format Print one line for every command: ADD: print OK. RESERVE: print <job_id> <token> or NONE. COMPLETE: print OK on success, otherwise IGNORED. FAIL: print RETRY when re-enqueued, DLQ when dead-lettered, or IGNORED for an invalid token/state. DLQ: print comma-separated job IDs, or EMPTY. Example Input: 6 ADD 0 taskA 1 RESERVE 0 5 RESERVE 5 5 FAIL 6 taskA 2 DLQ 6 RESERVE 6 1 Output: OK taskA 1 taskA 2 DLQ taskA NONE Example Input 5 ADD 0 a 2 RESERVE 0 10 COMPLETE 1 a 1 RESERVE 1 5 DLQ 1 Output OK a 1 OK NONE EMPTY