Sorting: Stable Sort by Key

Sorting: stable ascending sort by key

Each record is "an integer key + a label with no spaces". Sort by key, smallest first, and keep it stable: when two records share a key, their output order must match the input order.

This is a favourite exam point (e.g. sorting by a secondary key). Complete stableSortByKey, moving keys[] and labels[] together.

Pitfalls: (1) for stability, only swap/shift on a strictly greater comparison (use >, not >=); >= swaps equal keys and breaks stability. (2) Selection sort and quicksort do long-distance swaps and are inherently unstable — use a stable adjacent-comparison method like insertion or bubble. (3) When you move a key, move its label too, or the two arrays fall out of sync.

Input

• Line 1: integer n.
• Next n lines: an integer key and a label (space-separated; label has no spaces).

Output

• n lines: the records after a stable sort, each key label.

Example: input 4 / 3 a / 1 b / 3 c / 1 d -> 1 b / 1 d / 3 a / 3 c (b stays before d for key 1; a stays before c for key 3).