Arya and company reach Stoney Sept, a decent sized town. She kills some prisoners dying in cages, because whatever their crimes, nobody deserves that. Also it's unnerving that they're Stark men. They stay at an inn called ??? that also happens to be a knocking shop run by one Tansy. Could she be the Tansy that Lord Hoster was muttering about in his delerium? If so then Catelyn has the wrong end of the stick.
One of the prostitutes jokes that her dad might be King Robert. She has his hair, but Arya dismisses this because Gendry also has his hair. But she doesn't know that that's because Gendry is Robert's son. And the hair presumably is very significant, after all that's how this whole saga started, with a dead hand who got too close to the truth after noticing Joffrey was too blonde.
Gendry fancies Arya and is annoyed because she is too highborn for him, so he goes off in a huff. Arya doesn't notice and doesn't know why he's in a huff. As a king's bastard he's higher than he realises, though. High enough to marry Arya? Don't know. But I now predict Arya ends up on the iron throne with Gendry as king regent.
The mad huntsman has of Stoney Sept has caught a Lannister but it's not Jaime, Arya can tell. Who is it?