クイックソート

$n$ 枚のカードの列を整列します。１枚のカードは絵柄(S, H, C, またはD)と数字のペアで構成されています。これらを以下の疑似コードに基づくクイックソートで数字に関して昇順に整列するプログラムを作成してください。partition は ALDS1_6_B の疑似コードに基づくものとします。

1 quicksort(A, p, r)
2   if p < r
3     q = partition(A, p, r)
4     quickSort(A, p, q-1)
5     quickSort(A, q+1, r)

ここで、$A$ はカードが格納された配列であり、partition における比較演算はカードに書かれた「数」を基準に行われるものとします。

また、与えられた入力に対して安定な出力を行っているかを報告してください。ここでは、同じ数字を持つカードが複数ある場合、それらが入力で与えられた順序であらわれる出力を「安定な出力」とします。

入力

1行目にカードの枚数 $n$ が与えられます。

2行目以降で $n$ 枚のカードが与えられます。各カードは絵柄を表す１つの文字と数（整数）のペアで１行に与えられます。絵柄と数は１つの空白で区切られています。

出力

1行目に、この出力が安定か否か（StableまたはNot stable）を出力してください。

2行目以降で、入力と同様の形式で整列されたカードを順番に出力してください（$n$ を出力する必要はありません）。

制約

• $1 \leq n \leq 100,000$
• $1 \leq カードに書かれている数 \leq 10^9$
• 入力に絵柄と数の組が同じカードは２枚以上含まれない

入力例 1

6
D 3
H 2
D 1
S 3
D 2
C 1

出力例 1

Not stable
D 1
C 1
D 2
H 2
D 3
S 3

入力例 2

2
S 1
H 1

出力例 2

Stable
S 1
H 1

Note

Algorithm

 

---