stripped of almost all his lands by Llywelyn as punishment. Llywelyn consolidated his position in 1205 by marrying Joan, the natural daughter of King John. He had previously been negotiating with Pope Innocent III for leave to marry his uncle Rhodri's widow, daughter of Rǫgnvaldr Guðrøðarson, King of the Isles. However this proposal was dropped. In 1208, Gwenwynwyn of Powys fell out with King John who summoned him to Shrewsbury in October and then arrested him and stripped him of his lands. Llywelyn took the opportunity to annex southern Powys and northern Ceredigion and rebuild Aberystwyth Castle. In the summer of 1209 he accompanied John on a campaign against King William I of Scotland. Setback and recovery 1210–1217 In 1210, relations between Llywelyn and King John deteriorated. J. E. Lloyd suggests that the rupture may have been due to Llywelyn forming an alliance with William de Braose, 4th Lord of Bramber, who had fallen out with the king and had been deprived of his lands. While John led a campaign against de Braose and his allies in Ireland, an army led by Earl Ranulph of Chester, and Peter des Roches, Bishop of Winchester, invaded Gwynedd. Llywelyn destroyed his own castle at Deganwy and retreated west of the River Conwy. The Earl of Chester rebuilt Deganwy, and Llywelyn retaliated by ravaging the earl's lands. John sent troops to help restore Gwenwynwyn to the rule of southern Powys. In 1211, John invaded Gwynedd with the aid of almost all the other Welsh princes, planning according to Brut y Tywysogion "to dispossess Llywelyn and destroy him utterly". The first invasion was forced to retreat, but in August that year John invaded again with a larger army, crossed the River Conwy and penetrated Snowdonia. Bangor was burnt by a detachment of the royal army and the Bishop of Bangor captured. Llywelyn was forced to come to terms, and by the advice of his council sent his wife Joan to negotiate with the king, her father. Joan was able to persuade her father not to dispossess her husband completely, but Llywelyn lost all his lands east of the River Conwy. He also had to pay a large tribute in cattle and horses and to hand over hostages, including his illegitimate son Gruffydd, and was forced to agree that if he died without a legitimate heir by Joan, all his lands would revert to the king.