Speaking of Labyrinths, I just YASD'ed a DSCK of Xom from some early electric eels. He had +5 Int!
Well, labyrinth spawned at level 12. I find the minotaur. He picks up an artifact spear of freezing. (I had demonic guardian 2) a sixfirny spawns to help me, it dies in one turn while it closes in to melee him, by 2 hits of the spear and 1 headbutt. I started kiting him and more demons spawned, but they were smoke demons and sixfirnys, after a bunch of them died and one spawned, I just stood in a relatively open area so they could hit him while he tried to kill me and quaffed pots of cure wounds for a while. He was hitting me for like 30 dmg every turn. Granted, I was wearing a +2 robe. Well, finally he died and I got the spear - +2 +3 freeze, rC, MR. Meh.