Thornhill Secondary School is hosting its 17th annual debate tournament! You, as a debate tournament volunteer are helping organize the event. Your task is to decide the pairings for the next round of debates based on each team's win rate. A team's win rate is defined as simply the number of rounds that team already won. When pairing teams, you must match the team with the highest win rate against the team with the lowest win rate, then the team with the second highest win rate against the team with the second lowest win rate and so on. By doing this, you eliminate the inferior teams first and ensure a more balanced and climactic grand finals. Given the teams and the number of rounds they won, determine the pairings for the next round.

Input Specification

The first line of input is ~n~ ~(2 \le n \le 10^5)~ representing the number of teams in the tournament. This will always be an even number.
The next ~n~ lines each represent a team. These lines each have the following separated by a space:

• The name of the team containing alphanumeric characters and symbols but no spaces.
• The number of rounds this team won ~w~ ~(0 \le w \le 10^6)~. No two teams will have the same number of rounds won.

Output Specification

Starting from the team with the highest win rate to the team with the median win rate, output ~n / 2~ lines with the higher win rate team's name followed by their matchup's name separated by a space.

Sample Input

6
TSS_AB 10
Olympiads_QW 6
TSS_CD 9
Anatoly 0
Linked_Key1 2
Linked_Key2 3

Sample Output

TSS_AB Anatoly
TSS_CD Linked_Key1
Olympiads_QW Linked_Key2