If you're on a TLP server, get the cloudy stone of Veeshan from Sornita Eltern in Erudin..
To get to Plane of Sky give Relm M'Loch a cloudy potion of Veeshan. (Located by the PoK book in Plane of Tranquility)
To get to the Plane of Hate give Relm M'Loch a Fuligan Soulstone