java

For your first assignment, you are write a program that reads in a list of people's name, followed by a list of birthday gifts, and matches the gifts to the people. The match is easy - the first letter of the birthday gift must be the same as the first letter of the person's name. For example, "Bobbie Saxon" could get a "Baseball bar but not a "Football." "Xerxes Jones" could get a "Xerox machine." Note that not everyone may get a birthday gift - there may be no matching gift, and there may be birthday gifts that are not gifted. Details The program should read in a list of names from standard input, one name per line. Names always start with capital letters and may contain spaces. The special line END** will indicate the end of the list of names. Then the program should read in a list of birthday gifts, also one per line. The birthday gifts always begin with capital letters and may have spaces in them as well. Again, the special line END indicates the end of the list of birthday gifts. There are at most 100 names and at most 100 birthday gifts, but there could be fewer than 100 of each. A match occurs when the first letter of the name is the same as the first letter of a birthday gift. If more than one gift matches a person, it doesn't matter which gift is matched. There is just one of each birthday gift, that is, the program can't match the same gift with multiple names. It may be that a person doesn't get a gift, and it may be that a gift is not given to any person Input The input consists of a list of names, one name per line. Names may contain spaces. The list of names is ended by the special line "END". That list is followed by a list of birthday gifts, one per line. Birthday gifts may contain spaces. The list of birthday gift is ended by the special lineEND". The list of names and the list of birthday gifts are not in any particular order, i.e., not sorted, and there may not be the same number of names as birthday gifts. There are at most 100 names and at most 100 gifts, but there could be less than 100 of each Output The program will print out the names read in one per line. The order of the names printed out does not need to be the same as the order in which they are read in. If the name is matched with a birthday gift, the birthday gift is printed out on the same line, separated from the name by a comma. If the person is not matched with a birthday gift, only the name is printed out on the line. After all the names are printed out, the program will print out the special line **END". Then program will print out the list of birthday gifts that were not given out. Additional Requirements The program should be efficient. It should sort the list of names and sort the list of birthday gifts and then match the names with the gifts. Proceed through the two sorted lists in lockstep. If a name matches a birthday gift (the first letters match), then print out both on a line, and advance to the next item of each list. If the first letter of the name precedes the first letter of the birthday gift, then there is no matching gift for the person, so the program should print out just the name, and advance to the next name (but does not advance to the next gift.) If the first letter of the name comes after the first letter of the birthday gift, then the birthday gift will not be given out. Add the birthday gift to the list of ungiven gifts, and advance to the next birthday gift (but do not advance to the next name.) If the program runs out of names first, then the remaining birthday gifts are not given out and should be added to the list of ungiven gifts. If the program runs out of birthday gifts firsts, then the remaining names in the list won't be given gifts. After coming to the end of both lists, the program should print out ****END** followed by the list of ungiven gifts, one per line. The program may use arrays, or ArrayLists (if you know about them.) The program should read from standard input and write to standard output. This is important so that the program can be tested by an automated program