gets
a=$<.map{|l|a=l.split;[a[0],a[1].to_i,$.]}
g=->p,r{x=a[r]
i=p
(p...r).map{|j|a[j][1]<=x[1]&&(a[i],a[j]=a[j],a[i]
i+=1)}
a[i],a[r]=x,a[i]
i}
s=->f,p,r{p<r&&(q=g[p,r]
s[f,q+1,r])}
s[s,0,a.size-1]
puts a.map{|b|c=a.select{|d|d[1]==b[1]}
c!=c.sort_by{|d|d[2]}&&break}?:Stable:"Not stable",a.map{|e|e[0,2]*" "}