Championship Gifts

CPU usage time limit is 0.5 seconds

Runtime memory usage limit is 256 megabytes

On the planet Bitaculandia, there is an annual prestigious competition hosted by Miss M — an international team championship.

Residents from all countries of Bitaculandia participate in this competition. The championship also involves solving problems with very interesting legends, like this one, but in teams. The best teams, according to the championship results, receive prizes.

Miss M has finally received the long-awaited gifts for the championship, which need to be sent to the winners. She realized that there are many gifts. And while everything is clear with mugs and packets, there was a problem with T-shirts. Each team has three participants, and each of them ordered a T-shirt of one of $n$ colors and one of $m$ sizes. But Miss M is not sure that all the winners' wishes will be fulfilled...

Therefore, Miss M developed an algorithm according to which she will collect gifts for the teams.

If a T-shirt of the required size and color is still available, she takes it.
Otherwise, she looks for a T-shirt of the same size but a different color. If there are several, then the color with the minimum number.
Otherwise, she looks at T-shirts of the next larger size, but with the priority of the color indicated by the team at the beginning. If there are no T-shirts with the prioritized color, but there are several others, we choose the T-shirt with the minimum color number.
Otherwise, we repeat the process of the previous step among T-shirts of the next larger size. We continue this process until such sizes are available.
If none of the remaining T-shirts are suitable, then the T-shirt indicated by the team is recorded as absent.

Miss M decided that she needs to send back to the warehouse the T-shirts that turned out to be superfluous and order more of the T-shirts that she recorded as absent, to satisfy all the participants of the championship. To avoid sorting all the T-shirts by hand, Miss M asks you to write a program that:

Outputs which specific T-shirts turned out to be superfluous in the format of a table of size $n \times m$ , where $l_{ij}$ — the number of T-shirts of the $i$ -th color and $j$ -th size that remained after she distributed T-shirts to all participants.
Outputs which T-shirts need to be ordered in the format of a table of size $n \times m$ , where $n_{ij}$ — the number of T-shirts of the $i$ -th color and $j$ -th size that participants asked for, but the organizers could not give any T-shirts.

Input

The first line contains two integers $n$ and $m$ ( $1 \leq n \leq 100, 1 \leq m \leq 6$ ) — the number of different colors and sizes of T-shirts, respectively.

The second line contains $m$ elements — the sizes of T-shirts delivered to Miss M. Sizes are — XS, S, M, L, XL, 2XL. It is guaranteed that the sizes are given in increasing order.

Each of the following $n$ lines contains $m$ integers $t_{i 1}, t_{i 2}, \dots, t_{im}$ ( $0 \leq t_{ij} \leq 5 \cdot 1 0^{3}$ ) — the number of T-shirts of the $i$ -th color and $j$ -th size.

The next line contains one integer $k$ ( $1 \leq k \leq 1 0^{5}$ ) — the number of winners.

Each of the following $k$ lines contains an integer $c_{i}$ ( $1 \leq c_{i} \leq n$ ) and a character $s_{i}$ — the color and size of each T-shirt, respectively. It is guaranteed that $s_{i}$ is one of the $m$ sizes that were specified.

The winners' requests must be processed exactly in the order specified.

Output

In each of the following $n$ lines, output $m$ integers $l_{i 1}, l_{i 2}, \dots, l_{im}$ — the number of T-shirts of the $i$ -th color and $j$ -th size that remained.

In each of the following $n$ lines, output $m$ integers $n_{i 1}, n_{i 2}, \dots, n_{im}$ — the number of T-shirts of the $i$ -th color and $j$ -th size that need to be purchased.

Examples

Input

Answer

Note

Suppose we have white T-shirts (index one) and black T-shirts (index two). So, we have one white T-shirt of size S, and also three white T-shirts of size M. There are three black T-shirts of size S, and also three black T-shirts of size XL.

Consider each winner:

The winner needs a white T-shirt of size S, we have one, so we give it to him. This was the last such T-shirt.
The winner needs a black T-shirt of size XL, we have one, so we give it to him. We still have two such T-shirts left.
The winner needs a white T-shirt of size M, we have one, so we give it to him. We still have two such T-shirts left.
The winner needs a black T-shirt of size XL, we have one, so we give it to him. We still have one such T-shirt left.
The winner needs a white T-shirt of size M, we have one, so we give it to him. We still have one such T-shirt left.
The winner needs a black T-shirt of size M, we don't have one. However, we have a white T-shirt of size M, so we give it to him. We no longer have any white T-shirts of size M left.
The winner needs a white T-shirt of size M, we don't have one. We also don't have a black T-shirt of size M, so we can't give the winner a T-shirt of size M. Therefore, we look at the next size — XL. The winner wants to get a white T-shirt, but we also don't have such a T-shirt of size XL. So we give him a black T-shirt of size XL. This was the last such T-shirt.
The winner needs a black T-shirt of size S, we have one, so we give it to him. We still have one such T-shirt left.
The winner needs a white T-shirt of size XL, but we don't have either a white T-shirt of that size or a black one. Therefore, since we don't have T-shirts of a larger size, we can't give the participant the T-shirt he indicated, we record it on the list.

We are left with two black T-shirts of size S.

We could not give out one white T-shirt of size XL.

Submissions 13

Acceptance rate 15%