시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 550 163 115 32.213%

문제

1차원 공간에서의 선분, 2차원 공간에서의 직사각형, 3차원 공간에서의 직육면체를 생각해 보자.

선분의 크기는 변수 $A$로, 직사각형의 크기는 두 개의 변수 $A$와 $B$로, 직육면체의 크기는 세 개의 변수 $A$, $B$, $C$로 표현할 수 있다. 선분의 길이는 $A$, 직사각형의 넓이는 $A \cdot B$, 직육면체의 부피는 $A \cdot B \cdot C$이다.


4차원 공간에 네 개의 변수 $A$, $B$, $C$, $D$로 크기를 표현할 수 있는 초직사각형이 있다. 4차원 초직사각형의 부피는 $A \cdot B \cdot C \cdot D$이다.

처음에 변수 $A$의 값은 $A_0$, 변수 $B$의 값은 $B_0$, 변수 $C$의 값은 $C_0$, 변수 $D$의 값은 $D_0$이다.

이 초직사각형의 크기를 바꿀 수 있는 카드가 $N$장 있다. 이 중 $i$ ($1 \le i \le N$)번째 카드에는 문자 $T_i$ 와 자연수 $U_i$가 적혀 있다. $T_i$는 A, B, C, D 중 하나이며, 값을 바꿀 변수의 이름을 의미한다. $i$번째 카드를 사용하면, $T_i$에 해당하는 변수의 값이 $U_i$만큼 증가한다. 사용한 카드는 즉시 소멸하므로, 각각의 카드는 최대 한 번씩만 사용할 수 있다.

당신은 4차원 초직사각형의 부피를 최대화하고자 하며, 이를 위해 주어진 카드 중 정확히 $K$장을 골라서 원하는 순서대로 사용할 수 있다. 어떤 카드를 어떤 순서대로 사용해야 하는지를 구하여 출력하는 프로그램을 작성하라.

부피를 최대화하는 사용 방법이 여러 가지 있을 경우 그 중 하나만 구하여 출력하면 된다.

입력

첫 번째 줄에 두 개의 정수 $N$과 $K$가 공백 하나를 사이로 두고 주어진다.

두 번째 줄에 네 개의 정수 $A_0$, $B_0$, $C_0$, $D_0$가 공백 하나씩을 사이로 두고 주어진다.

다음 $N$개의 줄에는 카드들에 대한 정보가 주어진다. 이 중 $i$ ($1 \le i \le N$)번째 줄에는 $T_i$와 $U_i$가 공백 하나를 사이로 두고 주어진다.

출력

$K$개의 줄에 선택한 카드들을 사용할 순서대로 입력 형식과 같은 방식으로 한 줄에 한 카드씩 출력한다.

제한

  • 주어지는 모든 수는 정수이다.
  • $1 \le K \le N \le 200~000$
  • $1 \le A_0, B_0, C_0, D_0 ≤ 1~000~000$
  • 모든 $1 \le i \le N$에 대해, $T_i$는 A, B, C, D 중 하나이다.
  • 모든 $1 \le i \le N$에 대해, $U_i$는 $1$ 이상 $1~000~000$ 이하의 자연수이다.

서브태스크 1 (8점)

  • $N \le 10$
  • $A_0, B_0, C_0, D_0 \le 10$
  • 모든 $1 \le i \le N$에 대해 $U_i \le 10$이다.

서브태스크 2 (6점)

  • $B_0 = C_0 = D_0 = 1$
  • 모든 $1 \le i \le N$에 대해 $T_i$는 A이다.

서브태스크 3 (15점)

  • $N \le 300$
  • $A_0, B_0, C_0, D_0 \le 100$
  • 모든 $1 \le i \le N$에 대해 $U_i \le 100$이다.

서브태스크 4 (21점)

  • 모든 $1 \le i \le N$에 대해 $U_i = 1$이다.

서브태스크 5 (20점)

  • $D_0 = 1$
  • 모든 $1 \le i \le N$에 대해 $T_i$는 A, B, C 중 하나이다.
  • 모든 $1 \le i \le N$에 대해 $U_i \le 10$이다.

서브태스크 6 (30점)

  • 추가 제약 조건 없음.

예제 입력 1

4 3
1 1 1 1
A 1
A 1
A 2
A 2

예제 출력 1

A 2
A 1
A 2

예제 입력 2

8 6
1 2 3 4
A 2
A 5
B 7
B 2
C 5
C 9
D 1
D 3

예제 출력 2

A 2
B 7
C 5
A 5
C 9
D 3

채점 및 기타 정보

  • 예제는 채점하지 않는다.