Hoy. I don't have a walkthrough. I do remember where the keys are. There are three "Gardens of Mario" -- one on the road to the desert, one in the north between the desert and the green area to the northwest. And the third is an island on the southeast of the map, behind the giant mountain (there's also a power altar back there somewhere). These will lead you to one of the powers. It's been so long,... I don't remember fairies at all., sorry.