Lock Manager

Implement the Lock Manager for a Database Management System (DBMS).

Locks control concurrent access to data items by multiple transactions. This DBMS is simple and uses only two lock modes: Shared (S) and Exclusive (X). Each lock request consists of a lock mode (S or X), a transaction identifier, and a data item identifier. Multiple locks can be granted for the same data item at the same time, as long as none of them conflict.

Two locks for the same data item conflict if:

• they belong to different transactions, and
• at least one of them is an exclusive (X) mode lock.

Write a very simple lock manager. A lock request is granted only if it does not conflict with any lock already granted for that data item. Once granted, a lock is never released or changed in any way. If a lock request is denied because it conflicts with some previously granted lock, then the transaction that made the request is blocked, and every later request from that transaction is ignored.

The input consists of a number of lock requests, one request per line. Each request has the following format:

MODE TRID ITEM

• MODE is a single capital letter, S or X, denoting the requested lock mode.
• TRID is the transaction identifier and ITEM is the data item identifier. Both are integers greater than $0$, and each has at most $9$ decimal digits.

There are at least $1$ and at most $10000$ requests. The last request is followed by a line containing a single character #.

Process all requests in order. For each request, print one line with the response to that request. The allowed responses are:

• GRANTED — the request does not conflict with any previously granted lock and is granted.
• DENIED — the request conflicts with some previously granted lock and is denied, which blocks the requesting transaction.
• IGNORED — the requesting transaction was already blocked by an earlier request.

Print the responses in capital letters exactly as shown above. An arbitrary number of blank lines may follow the last response.