Under construction

Still being built. Things may change

Best Buddies

Interview

Time limit2sMemory limit256 MB

Summary
Sort all participants by last name then first name, split the order into consecutive triples, and print each queried person's two teammates.
Level

Easy3 of 10

Topics
Sorting, Hash map
Solved
No attempts yet

Problem

You signed up for a yearly collegiate programming contest. Unlike previous years, participants do not pick their own team mates. Instead, every participant is placed in a line in alphabetical order, and the line is cut into blocks of three: the first three participants form team 1, the next three form team 2, and so on. The number of participants NN is a multiple of 3, so every team has exactly 3 members.

Every participant has one first name and one last name, both written with the lower case letters a to z. No two participants share the same first name and last name. The alphabetical order compares last names in ascending lexicographic order first, and compares first names only when the last names are equal. So john smith comes after carla smith, but before bob taylor.

Given the name of a participant, print the names of that participant's two team mates.

Input

The first line contains the number of participants NN. (3≤N≤99 9993 \le N \le 99\,999, and NN is a multiple of 3)

Each of the next NN lines contains the first name and the last name of one participant, separated by a space. Both names are strings of lower case English letters with length at least 2 and at most 16.

The next line contains the number of queries QQ. (1≤Q≤N1 \le Q \le N)

Each of the next QQ lines contains the first name and the last name of one queried participant. Every queried participant appears in the list.

Output

For each query, print the two team mates of the queried participant in the alphabetical order described above, one participant per line. On each line, print the first name and the last name separated by a single space.

Examples6

  1. Example 1

    Input
    12
    john smith
    carla smith
    bob taylor
    alice watson
    sarah taylor
    ryan singh
    jessica li
    kevin wright
    charles lee
    megan davies
    ryan davies
    julia leung
    3
    ryan davies
    sarah taylor
    kevin wright
    
    Expected output
    megan davies
    charles lee
    alice watson
    kevin wright
    sarah taylor
    alice watson
    
  2. Example 2

    Input
    3
    zoe zulu
    am ab
    bo ab
    1
    am ab
    
    Expected output
    bo ab
    zoe zulu
    
  3. Example 3

    Input
    3
    al brown
    al adams
    bo adams
    3
    al adams
    bo adams
    al brown
    
    Expected output
    bo adams
    al brown
    al adams
    al brown
    al adams
    bo adams
    
  4. Example 4

    Input
    6
    ann kim
    an kim
    anna kim
    ab kim
    ba kim
    aa kim
    2
    an kim
    ba kim
    
    Expected output
    aa kim
    ab kim
    ann kim
    anna kim
    
  5. Example 5

    Input
    6
    qqqqqqqqqqqqqqqq qqqqqqqqqqqqqqqq
    ab ab
    zz zz
    zz qqqqqqqqqqqqqqqq
    ab zz
    aa aa
    2
    qqqqqqqqqqqqqqqq qqqqqqqqqqqqqqqq
    aa aa
    
    Expected output
    aa aa
    ab ab
    ab ab
    qqqqqqqqqqqqqqqq qqqqqqqqqqqqqqqq
    
  6. Example 6

    Input
    12
    lena ll
    kate kk
    jack jj
    iris ii
    hank hh
    gina gg
    finn ff
    eve ee
    dan dd
    carl cc
    bob bb
    alice aa
    4
    alice aa
    carl cc
    eve ee
    lena ll
    
    Expected output
    bob bb
    carl cc
    alice aa
    bob bb
    dan dd
    finn ff
    jack jj
    kate kk