Umayyad Caliph, Abd al-Malik ibn Marwan, to sue for peace in 688, agreeing to tender part of the taxes from Umayyad territory in Armenia, Iberia, and Cyprus, and to renew a treaty signed originally under Constantine IV, providing for a weekly tribute of 1,000 pieces of gold, one horse, and one slave. Justinian invaded the Caliphate again in 692, feeling that the Umayyads were in a weak position, but was repulsed at the Battle of Sebastopolis, where a large number of Slavs defected to the Umayyads, ensuring the Byzantine defeat. After this, the Umayyads renewed their invasion of North Africa, aimed at taking the city of Carthage in the Exarchate of Africa, and also invaded Anatolia. Around this time, Justinian imprisoned Leontius. Some Byzantine sources, such as Nikephoros and Theophanes, suggest that Justinian did so because he believed that Leontius was seeking to take the throne, but it is possible that the crushing defeat at Sebastopolis played a part in his imprisonment; as strategos of the Anatolic Theme, he likely served in the battle, and may have even been the main Byzantine commander in it. After further setbacks in the war, Justinian released Leontius in 695 because he feared losing control of Carthage, and appointed him strategos of the Theme of Hellas in Southern Greece. During his captivity, Leontius was cared for by two monks, Gregorios and Paulos, who prophesied his rise to the throne, and encouraged him to rise against Justinian after his release. Leontius, once free, quickly raised a rebellion against Justinian. Leontius had wide support from the aristocracy, who opposed Justinian's land policies, which restricted the aristocracy's ability to acquire land from peasant freeholders, and the peasantry, who opposed Justinian's tax policies, as well as the Blue faction (one of the Hippodrome factions), and the Patriarch of Constantinople Callinicus. Leontius and his supporters seized Justinian and brought him to the Hippodrome, where Justinian's nose was cut off, a common practice in Byzantine culture, done in order to remove threats to the throne, as mutilated people were traditionally barred from becoming emperor; however, Leontius did not kill Justinian, out of reverence for Constantine IV. After Justinian's nose was cut off, Leontius exiled him to Cherson, a Byzantine exclave in the Crimea. Reign and downfall Upon his coronation, Leontius, now known as Leo, adopted a moderate political stance. He restricted the activity of the Byzantine army, allowing small raids