Кольцевой буфер для логов

Реализуйте кольцевой буфер ёмкости cap для последних событий. Операции:

• push x: добавить x в конец; если буфер полон, самое старое событие вытесняется;
• pop: удалить и вывести самое старое событие, или empty, если буфер пуст;
• front: вывести самое старое событие, не удаляя, или empty.

Память выделите один раз: массив на cap элементов и индексы головы и размера, без сдвигов элементов.

Ввод: в первой строке cap и q (1 ≤ cap ≤ 10⁴, 1 ≤ q ≤ 10⁴), далее q операций. |x| ≤ 10⁹.

Вывод: ответы на pop и front, каждый с новой строки.

Пример 1

Ввод:

2 6
push 1
push 2
push 3
front
pop
pop

Вывод:

2
2
3

Пример 2

Ввод:

1 3
pop
push 5
front

Вывод:

empty
5