Hyper-Rectangle

Consider a line segment in one-dimensional space, a rectangle in two-dimensional space, and a rectangular box in three-dimensional space.

The size of a line segment is given by one variable $A$, the size of a rectangle by two variables $A$ and $B$, and the size of a rectangular box by three variables $A$, $B$, $C$. The length of the line segment is $A$, the area of the rectangle is $A \cdot B$, and the volume of the rectangular box is $A \cdot B \cdot C$.

In four-dimensional space there is a hyper-rectangle whose size is given by four variables $A$, $B$, $C$, $D$. The volume of the 4-dimensional hyper-rectangle is $A \cdot B \cdot C \cdot D$.

Initially, the value of variable $A$ is $A_0$, the value of variable $B$ is $B_0$, the value of variable $C$ is $C_0$, and the value of variable $D$ is $D_0$.

There are $N$ cards that can change the size of this hyper-rectangle. The $i$-th card ($1 \le i \le N$) has a letter $T_i$ and a positive integer $U_i$ written on it. $T_i$ is one of A, B, C, D and denotes the name of the variable whose value the card changes. Using the $i$-th card increases the value of the variable corresponding to $T_i$ by $U_i$. A used card disappears immediately, so each card can be used at most once.

You want to maximize the volume of the 4-dimensional hyper-rectangle. To do so, you may choose exactly $K$ of the given cards and use them in any order you like. Write a program that finds which cards to use and in what order.

If there are multiple ways to use the cards that maximize the volume, output any one of them.

The first line contains two integers $N$ and $K$ separated by a single space.

The second line contains four integers $A_0$, $B_0$, $C_0$, $D_0$ separated by single spaces.

The next $N$ lines give information about the cards. The $i$-th line ($1 \le i \le N$) contains $T_i$ and $U_i$ separated by a single space.

Output the chosen cards in the order they are used, one card per line, in the same format as the input, over $K$ lines.

• All given numbers are integers.
• $1 \le K \le N \le 200\,000$
• $1 \le A_0, B_0, C_0, D_0 \le 1\,000\,000$
• For every $1 \le i \le N$, $T_i$ is one of A, B, C, D.
• For every $1 \le i \le N$, $U_i$ is a positive integer between $1$ and $1\,000\,000$.