Comisia is sitting on a bench at a train station in Bucharest, waiting to board a train to Cluj-Napoca. Inside the waiting room, there are N ticket counters. Being bored, she decides to study the ticket counters.

A counter is either open (the ticket-seller is selling tickets) or closed (the ticket-seller is on a lunch break). While Comisia is waiting, the ticket-sellers take breaks and return multiple times. A queue is formed in front of each ticket counter, working by the first come, first served principle. When a counter closes, all the people waiting at that counter leave.

Our friend, Comisia, also notices that inside the waiting room, there are M other passengers, some of who are waiting to buy a ticket from one of the counters. Each passenger has a name and surname, strings which consist of lower case and upper case letters. It is known that all names are distinct, all surnames are distinct and all the names are different from all the surnames.

Because Comisia doesn't want you to be as bored as she is, she asks you to help her perform T operations, considering that at the beginning all the ticket counters are closed and there are no people waiting in line. The operations are:

1 x
Counter x changes its state (open/closed). If x closes then all the people waiting there leave.
2 x myName
A person with the name or surname myName queues at ticket counter x.
3 x
The first person waiting in line at counter x is served and then leaves the queue.
4 x
Comisia wants you to output on a line the full names (name + surname) of all the people waiting in line at counter x, from last to first. If there are no people waiting at counter x, output -1.
5 myName
Output the index of the queue where person myName is waiting. If the person is not part of a queue, output -1.


On the first line you are given N and M. The following M lines contain the name and surname of each passenger, separated by a blank space. The line after the names contains T, the number of operations, followed by T lines, each containing an operation in one of the given formats.


Print a line for each operation of type 4 or 5, as described above.


  • 1 ≤ N,M,T ≤ 100
  • The names and surnames have a maximum length of 20 letters.
  • Upper case letters are considered different from lower case letters.
  • It is guaranteed that all the given operations are possible.
  • The ticket counters are 1-based indexed, and so do the queues (eg. The first queue is number 1, the second queue is number 2 etc.).


5 3
Simion Tulea
Leonida Pascalopol
Costache Giurgiuveanu
1 1
2 1 Simion
2 1 Pascalopol
2 1 Giurgiuveanu
4 1
3 1
4 1
5 Costache
Costache Giurgiuveanu Leonida Pascalopol Simion Tulea
Costache Giurgiuveanu Leonida Pascalopol

Sponsors Gold