Problem K
King of Fighters explaine[d]
King of Fighters (KOF) is one of my favorite fighting games. So when I tried to make my own fighting games (though I never actually started¡), I took sometime investigating how the KOF system works.
After sometime, I came up with the following simple model:
- At any time, each person can be in one of its designed states (e.g. standing, running, jumping, punching etc).
- Each state has a set of frames.
- Each frame is an image (frame of animation) plus two areas: attacking area and weak area. Note that both areas can be composed of several disjoint regions.
- Taking into account both characters' positions, if one character's attacking area overlaps (with non-zero intersection area) with his opponent's weak area, the opponent gets hit.
- It's possible that both characters get hit at the same time.
(Athena in KOF97)
For simplicity, both attacking areas and weak areas are approximated by union of rectangles. The rectangles might be intersecting. Only their union represents the attacking areas and weak areas.
Your task is to decide, given the positions of these areas, who is getting hit.
Your task is to decide, given the positions of these areas, who is getting hit.
Input
The first line contains the number of test cases T(T<=100). Each test case contains two parts in the same format, describing the first character, then the second one. The first line of each part contains two integers a and w (0<=a,w<=5), the number of rectangles in the attacking area and weak area, respectively. Each of the a lines contains four non-negative integers x1, y1, x2, y2 (0<=x1<x2<=100, 0<=y1<y2<=100), that means the set of points (x,y) satisfying x1<=x<=x2, y1<=y<=y2 is in the attacking area. The next w lines describe the weak area in the same format.
Output
For each test case, print "First" if only the first character is hit, "Second" if only the second character is hit, "Both" if both are hit, "Neither" if neither is hit.
Sample Input
3
1 1
2 2 5 3
0 0 2 4
0 1
4 0 6 4
3 1
1 2 2 4
1 0 2 4
1 2 5 4
0 1 4 4
3 5
4 0 5 5
0 2 2 4
1 0 2 3
0 2 1 4
2 3 5 4
2 1 4 3
0 0 5 4
0 1 1 3
0 0
5 1
0 2 4 3
2 1 3 3
1 4 5 5
0 3 3 5
0 0 4 5
1 1 4 5
Output for the Sample Input
Case 1: Second
Case 2: Both
Case 3: Neither
Bonus
Be sure to test your program with the data provided in our gift package.
Rujia Liu's Present 6: Happy 30th Birthday to Myself
Special thanks: Md. Mahbubul Hasan, Feng Chen, SNK (for creating KOF series)