Monoid-Augmented FIFOs, Deamortised