Raffle Drum

Medium · design

A raffle drum holds numbered tickets. Inside, the tickets sit in a row of slots numbered 0, 1, 2, ..., and no ticket number appears twice. The drum starts empty. You are given a list of operations. operations[i] is "add", "remove" or "draw", and args[i] is its single argument.

"add" with ticket t: if t is not in the drum, put it in the first free slot at the end of the row and the result is 1. If it is already there, nothing changes and the result is 0.
"remove" with ticket t: if t is in the drum, take it out and the result is 1. The ticket in the last slot then moves into the slot that was just freed, so the row has no gaps (if t was itself in the last slot, the row just gets one slot shorter). If t is not in the drum, nothing changes and the result is 0.
"draw" with a number r rolled by the caller: the result is the ticket in slot r mod size, where size is the number of tickets in the drum. The ticket stays in the drum. If the drum is empty, the result is -1.

Operations are processed in the order given. Return a list with the result of every operation, in order.

Examples

Example 1

Input: operations = ["add", "add", "add", "draw", "remove", "draw"], args = [5, 8, 2, 4, 5, 4]

Output: [1, 1, 1, 8, 1, 2]

The row is 5, 8, 2. Draw 4 picks slot 4 mod 3 = 1, which holds 8. Removing 5 moves the last ticket, 2, into slot 0, so the row is 2, 8, and draw 4 now picks slot 0.

Example 2

Input: operations = ["add", "add", "remove", "remove", "draw"], args = [7, 7, 3, 7, 0]

Output: [1, 0, 0, 1, -1]

The second add finds 7 already inside, and removing 3 finds nothing. After 7 is removed, the drum is empty.

Example 3

Input: operations = ["draw", "add", "add", "remove", "draw", "draw"], args = [9, 4, 6, 4, 1, 2]

Output: [-1, 1, 1, 1, 6, 6]

Removing 4 moves 6 into slot 0, and it is then the only ticket, so every draw returns it.

Constraints

1 <= len(operations) <= 10^4
len(args) == len(operations)
operations[i] is add, remove or draw
0 <= args[i] <= 10^9