Problem D. Deadlock detector ≡

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:

• LOCK r — marks resource as locked by the calling task. If the resource is already locked by the same task, it does nothing. If it is locked by a different task, calling task is blocked (i.e. pauses execution and waits) until the resource is unlocked.
• UNLOCK r — unlocks given resource if it is locked by the current task, and does nothing otherwise.

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 N₁ N₂ M. Following lines contain N₁ locking primitives called by the first task, then N₂ 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 D₁ D₂, designating that deadlock can occur when the first task is trying to execute primitive number D₁ (1 ≤ D₁ ≤ N₁) while the second task is trying to execute primitive number D₂ (1 ≤ D₂ ≤ N₂).

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

Constraints

Sample tests

2 2 2
LOCK 1
LOCK 2
LOCK 2
LOCK 1

2 2

3 3 5
LOCK 5
LOCK 2
LOCK 3
LOCK 5
LOCK 3
LOCK 2

0

Explanation

Let us define the state function S: S_{i, j, k} = 1 if the task number i(i = 1, 2) has locked resource j(j = 1, M) after execution of primitive k(k = 1, N_i), and 0 otherwise. Additionally, let us define S_{i, j, 0} = 0. Values of S can easily be calculated either in a separate pass before main loop, or during the main loop as needed.

Deadlocks are obviously possible only between two locking primitives. We can analyze each pair of locking primitives p₁(p₁ = 1, N₁) and p₂(p₂ = 1, N₂), trying to lock resources r₁ and r₂ correspondingly. The condition of deadlock, derived straight from definition, is: S_{1, r2, p1 − 1} = 1 and S_{2, r1, p2 − 1} = 1.

Deadlock can be actually realized if pair of primitives p₁, p₂ can be executed simultaneously. This is possible in all cases except two.

Firstly, both primitives can be protected by common lock as shown in the second sample test. This condition can be formalized: there exists such r that S_{1, r, p1 − 1} = 1 and S_{2, r, p2 − 1} = 1.

Secondly, there may be a deadlock earlier which prevents execution from reaching pair p₁, p₂. Since the problem requires to output earliest of deadlocks, this case can be preventing if we check values of p₁ and p₂ in ascending order and stop after the first deadlock found.

This algorithms solves the problem using O(N₁ N₂ M) operations. The most expensive part of solution is checking for common locks. It can be performed in constant time if we notice that only one bit of state function can change on each step. This reduces complexity to O(N₁ N₂).