After a very productive art class, it's time for gym class. The gym teacher is away though, so your English teacher Joey is substituting. However, Joey isn't particularly athletic and doesn't know how to run a gym class properly. So, instead of teaching, he decides to have your class play dodgeball while he sits on a bench and solves problems on DM::OJ.
Your class comes to a mutual agreement to play a variant of the game called basketball dodgeball. The main objective is to shoot the dodgeballs into the enemy's basket.
After an hour of epic basketball dodgeball, the score is completely tied. One more goal and your team will win. Both teams have one ball that they need to score with. To ensure the best results, your team will try to pass the ball to the baller of the team.
The ball on both sides starts off in the hands of the player furthest back from the center line (it is guaranteed that only one player will meet this criterion). This player must get the ball to the baller. Everyone has a certain throwing range though, so this may involve several passes. Your goal as the strategist on your team is to figure the least amount of passes both teams need to take for the ball to get to their baller near the center line.
Since you go to a well-funded private school, both sides of the gym are squares whose areas are ~9\,000 \times 9\,000 m^2~. You are given the ~x~ and ~y~ coordinates of the players for both teams. The ~y~ coordinates indicate the distance a player is perpendicular to the net. A higher ~y~ coordinate on your team will indicate a player closer to your back end, and the same for the other team. You are also given the throwing range for each player, the distance they can throw the ball in meters. Only the baller will have a throwing distance of ~9\,001~, which is longer than the range of anyone else on the same team.
Figure out which team will win or whether it will be a draw, in which case your class will play an actual game of dodgeball as a tie breaker.
The first line will contain two integers, ~(2 \le N \le 3\,000)~ and ~(2 \le M \le 3\,000)~, the number of students in your team and the opposing team respectively. This will then be followed ~N~ lines representing the members of your team and ~M~ lines representing the members of the enemy team.
Each of these lines will be composed of three integers ~(0 \le X \le 9\,000)~, ~(0 \le Y \le 9\,000)~, and ~(0 \le R \le 9\,001)~, which are the ~x,y~ coordinates of each player and their range respectively. It is guaranteed that only 1 player on each team: the baller, will have a range of ~9\,001~.
If your team wins output
We are the champions!. If your team loses output
:'(. In the case of a draw, whether that be when the amount of passes for both teams are equal or when both teams will never be able to get their ball to their ballers, output
Sample Input 1
5 6 5 0 9001 3 3 10 2 3 5 3 10 7 4 11 2 5 0 9001 3 3 10 2 3 5 3 10 7 4 11 2 5 12 2
Sample Output 1
We are the champions!
Explanation for Sample Output 1
The ball starts off in the hands of the player in ~(4, 11)~, who passes it to the player in ~(3, 10)~, whose throwing range of ~10~ meters is enough to pass it directly to the baller at ~(5, 0)~. The enemy team has an additional person in the back that also has to pass, which means that it takes them ~4~ passes to get it to their goal as opposed to ~3~. ~4~ is greater than ~3~, so your team wins this game.
Sample Input 2
2 2 2000 2000 1000 1000 0 9001 999 0 9001 4 7 2
Sample Output 2
Explanation for Sample Output 2
The player at the back of your team is ~\approx 2\,828~ meters away from your baller, meaning his throwing range of ~1\,000~ is insufficient to reach the target. The player at the back of the opposing team is also too far away. Since both the teams are not able to get the ball to the basketball net, the game is declared a tie.
Sample Input 3
3 4 2222 4 2220 4 2222 2227 155 0 9001 42 73 9 42 64 64 42 0 9001 42 66 0
Sample Output 3