OK. You said you thought this could be done with relays. Here's one way to do it with relays, lots of diodes, and a few small components. No active semiconductors.
I've posted this design to show that it's possible, but it may not be practical, depending on your requirements, because of the...