Pirates On Parade

Time limit1sMemory limit128 MB

Summary
Sort pirates by height, then pair each shortest remaining pirate with the next one if their heights differ by at most 2 inches, and drop the rest.
Level

Easy3 of 10

Topics
Sorting, Greedy, Implementation
Solved
No attempts yet

Problem

Davy Jones wants his men to line up on parade. The pirates line up in pairs, ordered from shortest to tallest. However, the two pirates in a single pair may differ in height by at most 2 inches.

The pairing works as follows. Consider the pirates from shortest to tallest. Take the shortest pirate who is not yet paired; if the next shortest remaining pirate differs from him in height by at most 2 inches, the two of them form a pair. If no pirate is sufficiently near his height (within 2 inches) — or there are no pirates left — then this unpaired pirate is forced to walk the plank!

You may assume that no two pirates have exactly the same height.

Input

The input is a list of pirates. Each line contains a pirate's name and his height in inches as an integer.

Output

Print the pairs of pirates, one pair per line, ordered from the shortest pair to the tallest. In each pair, print the shorter pirate's name first. Any pirate forced to walk the plank must not be listed.

Examples2

  1. Example 1

    Input
    Sam 60
Dan 52
Bob 54
Art 61
    Expected output
    Dan Bob
Sam Art

  2. Example 2

    Input
    Sam 60
Dan 52
Bob 54
Kim 70
Art 61
    Expected output
    Dan Bob
Sam Art