Also, here's the thing. I do not want the original borders of Theodosius' division. I do not want the Byzies to conquer all the way to Egypt. Because as long as that happens, there will always be the possibility of horrible, unconscionable atrocities against people, as well as the possibility that some Byzie general would decide to loot Mecca for money. That is just wrong.
The world isn't a tea party, Tamerlane probably did as much atrocities as Genghis Khan or even more in this timeline, there is no way that the byzantine rule would be worse than their
Plus, the byzantine empire had a concept of many peoples living under their flag (like ottomanism), even the norsemen of the varangian guard settleted in their lands and converted, so it is way more likely a not-so-bloody conquest and then integration after the war than a mongol style invasion and looting