Problem D. Deadlock detector

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

Resource sharing is an important problem in parallel programming. When parallel tasks must use common resource, such as input/output channel, they serialize their access by using locks.

Two basic locking primitives are provided:

After the execution of the last locking primitive of the task, all resources locked by that task are unlocked.

Locking guarantees that only a single task can access the resource at a time. However, carelessly written programs may still lead to some unfortunate situations. If task A has already locked resource P and tries to lock Q, while task B has already locked Q and tries to lock P, they will both wait endlessly. This condition is called "deadlock".

Your program must, given lock/unlock sequences executed by two parallel tasks while accessing M resources, determine whether a deadlock is possible between them.

Input file format

First line of input file contains integers N1 N2 M. Following lines contain N1 locking primitives called by the first task, then N2 primitives called by the second task, in the order of calling.

Each primitive is located on a separate line and consists of a string LOCK or UNLOCK followed by one or more spaces and a resource number r (1 ≤ r ≤ M).

Output file format

Output file must contain integers D1 D2, designating that deadlock can occur when the first task is trying to execute primitive number D1 (1 ≤ D1 ≤ N1) while the second task is trying to execute primitive number D2 (1 ≤ D2 ≤ N2).

If there is more than one possible deadlock, output the one with minimal D1. If there is still more then one, output the one with minimal D2. If the deadlock is not possible, output file must contain a single 0 (zero).

Constraints

1 ≤ N1, N2 ≤ 5000, 1 ≤ M≤ 100.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 2 2
LOCK 1
LOCK 2
LOCK 2
LOCK 1
2 2
2
3 3 5
LOCK 5
LOCK 2
LOCK 3
LOCK 5
LOCK 3
LOCK 2
0

0.063s 0.009s 13