Hot and Cold Data Queue Simulation

We maintain a data queue (q) that consists of two sub-queues: a hot data queue (q_1) with capacity (n_1) and a cold data queue (q_2) with capacity (n_2). You are given (m) data page access requests. For each accessed data page (p), perform the following operations:

1. If (p) is not in (q) (i.e. not in (q_1) and not in (q_2)), load (p) and insert it at the head of (q_2). If (q_2) exceeds its capacity, evict the page at its tail.
2. If (p) is already in (q) and is in (q_1), remove it from its current position and re-insert it at the head of (q_1).
3. If (p) is already in (q) and is in (q_2), remove it from (q_2) and insert it into (q_1]. If (q_1) is full, first evict the page at the tail of (q_1). Moreover, if (q_2) is not full, the evicted page from (q_1) is moved to the head of (q_2); otherwise it is discarded.

After processing all requests, output the final state of (q_1) and (q_2) respectively. The pages in each queue should be printed from head to tail, with the elements separated by a single space.

inputFormat

The first line contains two integers (n_1) and (n_2), the capacities of the hot and cold queues respectively. The second line contains an integer (m), the number of data page access requests. Each of the following (m) lines contains an integer (p), representing a data page identifier.

outputFormat

Output two lines. The first line contains the pages in the hot data queue (q_1) from head to tail, separated by spaces. The second line contains the pages in the cold data queue (q_2) from head to tail, separated by spaces. If a queue is empty, output an empty line.

sample

2 2
5
1
2
1
3
4

1
4 3