Well-Matched Rivals (Hard Version)

Problem Description

$N$ students took the final exam and we have each student's information: name (a string of at most $8$ characters, no spaces), and scores in Chinese, Math, and English (natural numbers not exceeding $150$).

A pair of students $(i,j)$ is considered "well-matched rivals" if:

• The difference in each subject's score is at most $5$;
• The difference in total score is at most $10$.

Now we want to know which students are "well-matched rivals"; output their names.

All names are given in lexicographic order. The output should also list all rival pairs in lexicographic order:

1. Within each pair, the first name's lexicographic order should be smaller than the second name's;
2. If the first names of two pairs differ, output the pair whose first name is lexicographically smaller first;
3. If the first names are the same but the second names differ, output the pair whose second name is lexicographically smaller first.

Input Format

The first line contains a positive integer $N$, the number of students.

The following $N$ lines each start with a string (the student's name), followed by $3$ natural numbers (Chinese, Math, English scores). The string and the integers are separated by spaces.

Output Format

Output several lines, each containing $2$ space-separated strings representing one pair of well-matched rivals.

Output in the order described above.

Sample Input

3
fafa 90 90 90
lxl 95 85 90
senpai 100 80 91

Sample Output

fafa lxl
lxl senpai

Sample Explanation

There are $3$ students:

• fafa's Chinese, Math, and English scores are $90, 90, 90$, total $270$;
• lxl's Chinese, Math, and English scores are $95, 85, 90$, total $270$;
• senpai's Chinese, Math, and English scores are $100, 80, 91$, total $271$.

For fafa and lxl:

• The three subject differences are $5, 5, 0$, all $\le 5$;
• The total-score difference is $0$, $\le 10$. So they are well-matched rivals.

For fafa and senpai:

• The Chinese difference is $10$, $> 5$. So they are not well-matched rivals.

For lxl and senpai:

• The three subject differences are $5, 5, 1$, all $\le 5$;
• The total-score difference is $1$, $\le 10$. So they are well-matched rivals.

Therefore, outputting these two pairs in lexicographic order gives the two lines in the sample output.

Constraints

Names have length at most $8$; Chinese, Math, and English scores are natural numbers not exceeding $150$.