Once upon a time there was Flatland, a world whose inhabitants believed was a 2D rectangular region. Flatlanders (the people inhabiting Flatland) assumed that if somebody traveled long enough in one direction, he/she would fall down over the edge of Flatland. Animated Caribbean Movies (ACM) plans to produce a film about Flatland. Before the script of the film is approved, ACM wants to become familiar with life as it was in Flatland by simulating how the world could evolve from given initial situations and some conditions determining life and death. Flatlanders were nomads by nature as they were always traveling: all of them traveled at the same speed rate on straight lines but each individual had its own direction. As you may imagine, if one observed the life of a lonely Flatlander, he/she would eventually reach Flatland’s edge and die. Nevertheless, if two Flatlanders collided, then their fate was improved as their directions changed: the resulting directions were as the former ones reflected in a mirror bisecting the angle between the former directions of the crashing inhabitants. So, a Flatlander survived because a collision with another one could change his/her direction. However, there were bad news when more than two Flatlanders collided in a single crash: in that case all of them died, disappearing right there. Note that some Flatlanders could die at the same time. If this was the case, the last name of the list of deads was remembered as the Last Dead One in that moment (to simplify, we assume they used our modern English alphabet and lexicographic order). The survivors venerated the name of the Last Dead One until a new last dead appeared (and some Flatlander disappeared). ACM’s film begins with a given population in Flatland, where names, positions, and directions of every single individual are known. ACM wants you to help them to determine which would be the name of the last Last Dead One in the whole Flatland’s life. Input There are NC test cases to solve, 0 < NC < 100. The first line of the input file has NC. After that, for each testcase, a set of lines: • the first line contains a number n, the number of Flatlanders in the initial world (1 ≤ n ≤ 100); • the second line contains two positive integer numbers B and H separated by a space, representing the dimensions of Flatland (2 ≤ B,H ≤ 100). Coordinates in Flatland are points (i,j), with 0 ≤ i ≤ B, 0 ≤ j ≤ H. Flatland’s edges are points with coordinates of the form (0, j), (i, 0), (B, j) or (i,H); • n lines (one per Flatlander) with four numbers and one string: x,y,d1,d2 and name separated by a blank. (x,y) represents the position of the Flatlander (0 < x < B, 0 < y < H, and two Flatlanders cannot start in the same position), (d1, d2) represents the direction: (d1, d2) is a point on some Flatland’s edge, so that the Flatlander is moving towards it; name is a string of one to 10 alphabetical uppercase characters, which represents the name of the Flatlander. You may assume that every Flatlander has a unique name. Output For each given case, output one line with the name of the Last Dead One.
2/2 Sample input 2 2 20 23 1 1 0 0 BOB 3 3 3 0 ALICE 3 20 23 2 2 4 0 ALICE 4 2 2 0 BOB 1 3 0 3 CHARLES Sample Output ALICE BOB