시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 80 25 20 32.258%

문제

가희와 친구들은 읽기 쓰기 놀이를 하고 있습니다. 읽기 쓰기 놀이는 문자열을 가지고 시작합니다. 

놀이에서 사용하는 카드에 적혀져 있는 연산은 둘 중 하나입니다.

  • add c
    • 문자열 뒤에 문자 c를 추가합니다. 
  • del x
    • x번째 위치에 있는 문자열을 삭제합니다.
    • 문자열의 인덱스는 0부터 시작합니다. x번째 위치에 있는 문자를 삭제할 수 없는 경우에는, 오류가 발생합니다.

놀이의 규칙은 다음과 같습니다.

  • 빈 문자열로 게임을 시작합니다.
  • 각 턴을 수행하는 사람은 1명입니다.
  • 턴을 수행하는 사람은 가지고 있는 카드에 적혀져 있는 연산을 모두 수행하고 턴을 종료합니다. 턴을 수행하다가, 오류가 발생하면 문자열은 "ERROR"가 되고, 즉시 게임이 종료됩니다.
  • 게임의 끝났을 때, 문자열이 빈 문자열이라면, 문자열은 "EMPTY"가 됩니다.

문자열 게임에 참가하는 사람은 N명이고, 카드는 C장 있습니다.

게임에 참가하는 사람이 어떤 순서대로 카드를 냈는지 알고 있을 때, 게임의 결과로 나올 수 있는 문자열을 사전순으로 출력해 주세요.

입력

1번째 줄에 N, C가 공백으로 구분되어 주어집니다.

2번째 줄 부터 N+1번째 줄까지 1번 사람부터 N번 사람까지 낸 카드의 갯수와 카드를 낸 순서가 주어집니다.

예를 들어 3번째 줄에 3 2 4 5 가 있다면, 2번째 사람이 3개의 카드 2,4,5를 순서대로 낸 것을 의미합니다.

N+2번째 줄부터 N+C+1번째 줄까지 1번 카드부터 C번 카드에 적혀져 있는 1개 이상의 연산이 주어집니다.

연산이 여러 개 있는 경우에 각각의 연산은 ,으로 구분되어 주어집니다.

출력

게임의 결과로 나올 수 있는 문자열을 사전순으로 출력해 주세요.

만약에 같은 문자열이 여러 개가 나오면 하나로 출력해야 합니다.

제한

  • 1 ≤ N ≤ 9
  • 1 ≤ 카드 C개에 있는 연산 갯수 합 ≤ 10
  • 추가되는 문자는 소문자입니다.
  • 0 ≤ 제거 연산에서 등장하는 수 ≤ 9 
  • 카드에는 하나 이상의 연산이 있습니다.
  • 모든 플레이어는 최소 한 장의 카드를 냅니다.
  • 모든 카드는 게임에 이용되며, 한 번 사용된 카드는 다시 사용되지 않습니다.

예제 입력 1

2 2
1 1
1 2
ADD a,ADD a,ADD d
DEL 0

예제 출력 1

ERROR
ad

가능한 가짓수에 대한 설명은 다음과 같습니다.

  • 1번 사람이 먼저 1번 카드에 있는 연산들을 모두 수행한 후에 문자열은 "aad"가 됩니다. 
    다음에 2번이 2번 카드에 있는 연산을 모두 수행한 후에는, "aad"의 0번째 원소인 "a"가 지워집니다. 최종적으로 "ad"가 됩니다.
  • 2번 사람이 먼저 2번 카드 연산을 수행할 경우. 문자열은 처음에 비어 있습니다. 비어 있는 문자열의 0번째 원소에 접근을 시도하므로, 에러입니다.

아래의 플레이는 턴을 수행하는 사람은 카드에 적혀져 있는 모든 명령을 수행하고 턴을 종료한다는 조건을 만족하지 않습니다.

  • 1번은 1번 카드에 있는 ADD a 연산을 수행합니다.
  • 2번은 2번 카드에 있는 DEL 0 연산을 수행합니다.
  • 1번은 1번 카드에 있는 ADD a 연산과 ADD d 연산을 수행합니다.

예제 입력 2

2 3
2 1 2
1 3
ADD a
ADD b
ADD c

예제 출력 2

abc
acb
cab

예제 입력 3

2 2
1 1
1 2
DEL 0
DEL 0

예제 출력 3

ERROR

가능한 가짓수에 대한 설명은 아래와 같습니다.

  • 2번이 먼저 DEL 0을 수행하려는 경우 빈 문자열에 DEL 0을 수행하므로 ERROR입니다.
  • 1번이 먼저 DEL 0을 수행하려는 경우 빈 문자열에 DEL 0을 수행하므로 ERROR입니다.

게임의 결과로 나올 수 있는 문자열은 "ERROR", "ERROR"입니다. "ERROR" 문자열이 중복해서 나왔으므로, "ERROR" 문자열 하나로 출력해야 합니다.

출처

Contest > 가희와 함께 하는 코딩 테스트 > 가희와 함께 하는 1회 코딩 테스트 6번