Assistant Lab Assignment

To mark World Science Day, LG University prepared a science experiment event that the general public can join. Many participants are expected, so three large auditoriums on campus will be used as laboratories. The auditoriums are named A, B, and C, and the laboratories take the same names.

For everyone's safety, each auditorium gets enough experiment assistants, and backup assistants will also be assigned in case of an emergency.

A total of n people applied to be backup assistants, and at most nA, nB, and nC backup assistants are to be assigned to auditoriums A, B, and C respectively. A person can be assigned to at most one laboratory, and since each person prefers a different auditorium, this must be taken into account.

For example, consider n = 4 and nA = nB = nC = 1. The people are numbered 1 through 4.

• Only person 1 applied to laboratory A, and only person 1 applied to laboratory B.
• People 2 and 3 applied to laboratory C.
• Person 4 applied nowhere.

Here nC = 1, so people 2 and 3 cannot both be assigned to laboratory C; at most one of them can. Person 1 can be assigned to laboratory A or laboratory B, but not to both at once. Therefore at most two backup assistants can be assigned in this example.

Given n, nA, nB, nC and the lists of people who want to be backup assistants in each auditorium, determine how to assign as many people as possible.

The first line gives the number of test cases T.

In each test case, the first line gives n, and the next line gives nA nB nC separated by spaces.

The following three lines each give the list of people who applied to a laboratory. The first line gives mA, the number of people who applied to laboratory A, followed by the numbers of mA people separated by spaces. The next line gives mB, the number of people who applied to laboratory B, followed by the numbers of mB people separated by spaces. The next line gives mC, the number of people who applied to laboratory C, followed by the numbers of mC people separated by spaces.

Each person's number is a positive integer between 1 and n inclusive. The same person never appears more than once in an applicant list.

For each test case, print the number of people assigned as backup assistants on the first line.

If that number is x, print x more lines, each giving a person's number and a laboratory name (one of A, B, C) separated by a space.

If there are multiple ways to assign the maximum number of backup assistants, print any one of them.

• 1 ≤ T ≤ 10
• 1 ≤ n ≤ 10,000
• 1 ≤ nA, nB, nC ≤ n
• 0 ≤ mA, mB, mC ≤ n