What are possible solutions to add a watermark to the video on request?

Question

I'm looking for existing options to stream a video with the personalized watermark.

In this question, I mostly exclude the cost, performance, throughput, etc.

1. The first simple solution is to pre-generate a pool of watermarked videos and use them by dynamically linking some watermark identifiers with the user

2. I see AWS MedaLive can stream with the overlay, but this requires an additional effort to rewind and even more effort to rewind.

Is there a reasonable simple approach that can embed a watermark?