ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU contest. Petrozavodsk training camp. Summer 2010

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Warlord of the Army of Mages

Time limit: 0.5 second
Memory limit: 64 MB
After government of the Kingdom of Mages had formed a new army, they had to elect its warlord. Two wisest Masters, head of the Kingdom Zagamius and lich Sandro, decided to interview some candidates. They entered two different cabinets and started to invite certain mages for an interview or let go the mages they already talked to. Sandro and Zagamius could call the same mage for an interview several times and there could be more than one mage in their cabinets at some moments.
Each Master defined an order in which he will invite mages and let them go. If at certain moment both Masters can perform an action, then one of them performs it and the other one waits for him. In some cases only one Master can perform his action. For example, if Sandro invites a mage a, and this mage is being interviewed by Zagamius at that moment, then Sandro will wait until the mage a is free.
Unfortunately, there can be a situation when both Masters will wait for each other. In that case they won't elect the warlord of the army of mages and will lose a war that haven't yet started. Your should determine whether such a stupid defeat is possible.


The first line contains the number of test cases t (1 ≤ t ≤ 10). Each test case starts with a line containing space-separated integers n, m and k (1 ≤ n, m, k ≤ 1 000), which are the number of actions planned by Sandro, the number of actions planned by Zagamius and the number of mages in the new army. Mages are numbered with integers from 1 to k. The next n lines contain the Sandro's plan. Each line contains a sign “+” or “-” and an integer i (1 ≤ ik). Sign “+” means that Sandro wants to invite the i-th mage, and sign “-” means that he wants to let him go. The next m lines contain the plan of Zagamius in the same format. In both plans Masters let a mage go only if he is present in his cabinet. It is guaranteed that no Master will invite a mage if he is already present in his cabinet. If all the planned actions are performed, the cabinets of both Masters will be empty.


For each test case, output “:-)” if both Masters will certainly perform all the planned actions and will elect the warlord. In the other case, output “:-(”.


4 4 2
+ 1
+ 2
- 2
- 1
+ 1
+ 2
- 2
- 1
4 4 2
+ 1
+ 2
- 1
- 2
+ 2
+ 1
- 2
- 1
Problem Author: Eugene Kurpilyanskiy
Problem Source: Ural SU Contest. Petrozavodsk Summer Session, August 2010
To submit the solution for this problem go to the Problem set: 1844. Warlord of the Army of Mages