Rate limiter на токен-бакете для middleware на Go

Смоделируйте rate limit middleware: у каждого клиента свой бакет ёмкости b токенов, который пополняется на 1 токен каждые p мс (непрерывно, дробные токены копятся), но не больше b. В момент первого запроса клиента его бакет полон. Запрос пропускается, если в бакете есть хотя бы один целый токен, и тогда токен списывается.

Ввод: b p n (1 ≤ b ≤ 1000, 1 ≤ p ≤ 10⁶, 1 ≤ n ≤ 2000), затем n строк клиент время_мс, время не убывает (общее для всех клиентов, до 10¹²).

Вывод: allow или deny на каждый запрос, затем строка allowed K.

Пример

2 100 6
A 0
A 0
A 0
A 50
A 100
B 100

allow
allow
deny
deny
allow
allow
allowed 4