The Medieval history of Cyprus starts with the division of the Roman Empire into an Eastern and Western half. Byzantine period After the division of the Roman Empire into an eastern half and a western half, Cyprus came under the rule of Byzantium. The cities of Cyprus were destroyed by two successive earthquakes in 332 and 342 AD and this marked the end of an era and at the same time the beginning of a new one, very much connected with modern life in Cyprus. Most of the cities were not rebuilt, save Salamis which was rebuilt on a smaller scale and renamed Constantia after the Roman Emperor Constantius II, son of Constantine the Great, residing in Constantinople. The new city was now the capital of the island. It was mainly Christian and due to this some alterations were made during the rebuilding. The palaestra was turned into a meeting place and many architectural elements were used to erect spacious churches decorated with murals, mosaics and coloured marbles. The main event in Cyprus in this period was the spreading of the Christian faith. At that time, its bishop, while still subject to the Church, was made autocephalous by the First Council of Ephesus. People were engaged very much in matters of faith, especially fighting the effort of the Eastern Orthodox Patriarch of Antioch to put the Church of Cyprus under his control. They were finally successful in 488, when Archbishop Anthemius guided by a dream discovered the tomb of Barnabas with the saint's body lying in a coffin and on his chest a copy of the Gospel of Matthew in Barnabas' own writing. Having the relics with him, Anthemius dashed to Constantinople and presented them to Emperor Zeno. The latter was very much impressed and he not only confirmed the independence of the Church of Cyprus but he also gave to the Archbishop in perpetuity three privileges that are as much alive today as they were then, namely to carry a sceptre instead of a pastoral staff, to sign with red ink and to wear a purple cloak during services. By the beginning of the 7th century, the patriarch of Alexandria was John the Merciful from Amathus. Another important Cypriot of the time is the church writer Leontios of Neapolis. Arab conquest and Arab–Byzantine condominium In 649 AD the Arabs made the first attack on the island under the leadership