#P17068. [ICPC 2017 Shenyang R] Defense of the Ancients

[ICPC 2017 Shenyang R] Defense of the Ancients

Problem Description

In the game of Defense of the Ancients, a team has nn units and the other team has mm towers. Each unit and tower has some hit points (HP) and a fixed attack power (AP). The units (resp. towers) with positive HP are surviving and can attack the towers (resp. units), and the units (resp. towers) with zero HP are dead (resp. destroyed) and cannot attack anything.

The game is real-time and the time goes continuously. If a tower (resp. unit) is being attacked by kk units (resp. towers) with the AP of a1,a2,,aka_1, a_2, \dots, a_k at the same time, then its HP will continuously decrease with the rate of a1+a2++aka_1 + a_2 + \dots + a_k per second. There is no restriction on attack ranges. That is, any unit can attack any towers and vice versa.

During the whole game, the surviving units (resp. towers) will attack a selected tower (resp. unit) together until it has been destroyed (resp. killed). That is, the surviving units (resp. towers) will focus to destroy (resp. kill) the towers (resp. units) one by one.

If all the units are killed and there is at least a surviving tower, the tower team wins. If all the towers are destroyed and there is at least a surviving unit, the unit team wins. If all the units are killed and all the towers are destroyed at the same time, the game ends in a tie.

Both teams play optimally. Your task is to predict the winner of the game.

Input Format

The first line is the number of test cases up to 10.

For each test case, there are 5 lines. The first line contains two integers nn and mm (0<n1050 < n \le 10^5, 0<m1050 < m \le 10^5). The second line contains nn integers, which are the HP of the units. The third line contains nn integers, which are the AP of the units. The fourth line contains mm integers, which are the HP of the towers. The fifth line contains mm integers, which are the AP of the towers.

All the HP and AP are positive and less than 2322^{32}.

Output Format

For each test case, if the unit team has a winning strategy, output “Units win”, if the tower team has a winning strategy, output “Towers win”, if the game ends in a tie, output “Tie”.

3
1 1
10
10
9
11
2 2
1 1
5 4
2 1
4 2
3 3
1 2 3
1 4 9
1 4 9
1 2 3
Units win
Towers win
Tie