my @oldlist = map {chomp; $_} <DATA>;

my @sorted = map {$_->[2] . " " . $_->[1]}
             sort {($a->[2] cmp $b->[2]) || ($b->[1] cmp $a->[1])}
             map { [split] } @oldlist;
my @newlist = map {shift(@oldlist) . ' ' . $_} @sorted;

print join "\n", @newlist;
__DATA__
a1 p1 q5
a1 p1 q6
a1 p2 q4
a2 p3 q9
a2 p2 q8
a2 p2 q9