This was the low point of Llywelyn's reign, but he quickly recovered his position. The other Welsh princes, who had supported King John against Llywelyn, soon became disillusioned with John's rule and changed sides. Llywelyn formed an alliance with Gwenwynwyn of Powys and the two main rulers of Deheubarth, Maelgwn ap Rhys and Rhys Gryg, and rose against John. They had the support of Pope Innocent III, who had been engaged in a dispute with John for several years and had placed his kingdom under an interdict. Innocent released Llywelyn, Gwenwynwyn and Maelgwn from all oaths of loyalty to John and lifted the interdict in the territories which they controlled. Llywelyn was able to recover all Gwynedd apart from the castles of Deganwy and Rhuddlan within two months in 1212. John planned another invasion of Gwynedd in August 1212. According to one account, he had just commenced by hanging some of the Welsh hostages given the previous year when he received two letters. One was from his daughter Joan, Llywelyn's wife, the other from William I of Scotland, and both warned him in similar terms that if he invaded Wales his magnates would seize the opportunity to kill him or hand him over to his enemies. The invasion was abandoned, and in 1213, Llywelyn took the castles of Deganwy and Rhuddlan. Llywelyn made an alliance with Philip II Augustus of France, then allied himself with the barons who were in rebellion against John, marching on Shrewsbury and capturing it without resistance in 1215. When John was forced to sign Magna Carta, Llywelyn was rewarded with several favourable provisions relating to Wales, including the release of his son, Gruffydd, who had been a hostage since 1211. The same year, Ednyfed Fychan was appointed seneschal of Gwynedd and was to work closely with Llywelyn for the remainder of his reign. Llywelyn had now established himself as the leader of the independent princes of Wales, and in December 1215, led an army which included all the lesser princes to capture the castles of Carmarthen, Kidwelly, Llanstephan, Cardigan and Cilgerran. Another indication of his growing power was that he was able to insist on the consecration of Welshmen to two vacant sees that year, Iorwerth, as Bishop of St. David's, and Cadwgan, as Bishop of Bangor. In 1216, Llywelyn held a council at Aberdyfi to adjudicate on the territorial claims of the lesser princes,