아이템 거래

게임 개발자인 당신은 사용자들의 아이템 거래 시스템을 구현했다. 구현한 아이템 거래 시스템이 제대로 동작하는지 확인하기 위해 다음과 같이 테스트를 해보려고 한다.

거래 시스템에서 한 사용자가 다른 사용자에게 거래 요청을 하면 두 사용자들에게 거래 창이 뜨고 거래가 시작된다. 사용자들은 거래 창에 서로 교환할 아이템들을 올려놓는다. 거래가 진행되는 동안 여러 번 아이템을 올려놓을 수 있다. 두 사용자가 모두 거래를 수락하면 아이템들이 서로 교환되고 거래가 끝난다.

거래가 진행되는 동안 언제든지 거래 취소가 가능하며, 거래를 취소하면 해당 거래는 끝난다. 거래 취소의 경우에는 한 사용자만 취소해도 해당 거래가 취소된다. 거래를 수락한 사용자도 다시 거래를 취소할 수 있다. 한 사용자가 동시에 여러 거래를 진행할 수 없으며, 하나의 거래가 끝나야만 다음 거래를 진행할 수 있다.

A 사용자와 B 사용자의 거래가 진행되는 동안 거래 시스템으로 다음과 같은 정보들이 전달된다.

• A 사용자가 B 사용자에게 거래 요청 (또는 B 사용자가 A 사용자에게 거래 요청)

• A 사용자가 거래 창에 아이템 올려놓기 (여러 번 가능)

• B 사용자가 거래 창에 아이템 올려놓기 (여러 번 가능)

• A 사용자가 거래 수락

• B 사용자가 거래 수락

• A 사용자가 거래 취소

• B 사용자가 거래 취소

거래 시스템은 위 정보들을 받아서 처리하게 되는데, 두 사용자로부터 모두 수락을 받으면 그 때 아이템들을 서로 교환해준다. 사용자가 거래를 취소할 수도 있으므로 반드시 두 사용자에게 모두 수락을 받은 후 아이템이 교환되어야 한다.

동시에 여러 거래가 이루어질 수 있으므로, 거래 시스템에는 여러 거래의 정보들이 서로 섞여서 들어오게 된다. 거래 시스템은 각 거래의 정보를 들어온 순서대로 하나씩 처리한다. 들어온 거래 정보를 모두 처리했을 때, 사용자들의 아이템 상태를 출력 하시오.

입력 형식

입력의 첫 줄에는 사용자의 수 $N$이 주어진다. 사용자들은 순서대로 $1$부터 $N$까지의 고유한 번호를 가진다. ($1 \le N \le 100$) 다음 $N$줄에 각 사용자가 가지고 있는 아이템의 정보가 주어진다. $i$번째 줄에는 $i$번 사용자가 가지고 있는 아이템의 수가 주어지고, 각 아이템의 이름이 공백으로 구분되어 주어진다. 각 사용자가 가지고 있는 아이템의 수는 $1$ 이상 $100$ 이하이다.

각 거래에는 식별을 위한 거래 번호가 주어지는데, 첫 거래 요청은 $1$번이고 그 이후 새로운 거래 요청이 있을 때마다 $1$씩 증가한다.

다음 줄에 처리해야 할 전체 거래 정보의 수 $L$이 주어진다. ($1 \le L \le 100$) 다음 $L$줄에 거래 정보들이 주어진다. 각 거래 정보는 <거래 종류>와 <거래 번호>로 시작하며 거래 종류에 따라 다음과 같은 형식을 가진다. 거래 종류는 “거래 요청”은 B, “아이템 올려놓기”는 M, “거래 수락”은 E, 거래 취소는 R로 나타낸다. 아래 형식에서 거래 번호는 모두 X로 나타내었다.

• B X i j - 거래 요청: $i$번 사용자가 $j$번 사용자에게 거래 요청. 거래 번호는 $X$.
• M X i a - 아이템 올려놓기: $i$번 사용자가 거래 번호 $X$의 거래 창에 아이템 $a$ 올려놓기.
• E X i - 거래 수락: $i$번 사용자가 거래 번호 $X$의 거래를 수락.
• R X i - 거래 취소: $i$번 사용자가 거래 번호 $X$의 거래를 취소.

아이템 이름은 영어 소문자로만 주어지며, 이름의 길이는 $1$자 이상 $10$자 이하이다. 유효한 거래 정보들만 입력으로 주어진다. 예를 들어, 이미 종료된 거래에 대한 거래 정보, 가지고 있지 않은 아이템을 올려놓기, 이미 수락하여 진행중인 거래에 대해 다시 거래 수락, 현재 거래가 진행중인 사용자가 다른 거래를 요청, 현재 거래를 진행중인 사용자에게 거래 요청 등 유효하지 않거나 불필요한 입력은 들어오지 않는다.

출력 형식

주어진 거래 정보를 순서대로 모두 처리하고 난 후, 사용자들이 가진 아이템 정보를 $N$줄에 걸쳐 다음과 같은 형식으로 출력한다. $i$번째 줄에는 $i$번 사용자가 가진 아이템들을 사전순으로 출력한다.

예제 1

4
1 sword
1 shield
1 sword
1 shield
7
B 1 1 2
M 1 1 sword
M 1 2 shield
E 1 1
B 2 3 4
M 2 3 sword
R 2 4

sword
shield
sword
shield

예제 2

2
2 sword sword
2 shield shield
5
B 1 1 2
M 1 1 sword
M 1 2 shield
E 1 1
E 1 2

shield sword
shield sword

채점 방식

전체 입력 케이스들 중 답을 맞춘 입력 케이스 개수에 비례하여 점수를 받는다.

해설