Problem Description

There are $N + M$ color-shifting balls uniquely numbered between $0$ and $10^9$, inclusive. Among those, $N$ balls have a solid red or solid black color (also referred to as colored balls), and $M$ balls have an open-color. A ball with an open-color will shift its color into either red or black if it is put into a container together with at least one colored ball. Specifically, the open-color ball will shift its color into the same color as the colored ball in the container which has the closest number (i.e. minimum absolute difference) to the open-color ball number. If there are two colored ball numbers with the same absolute difference with the open-color ball number, the open-color ball number will shift its color into the same color as the colored ball which has the less number between the two.

For example, let there be 4 colored balls in a container: $(3,\text{red})$, $(6,\text{black})$, $(12,\text{red})$, and $(14,\text{black})$. If we put an $(9,\text{open})$ ball into the container, then it will shift its color into black because $(6,\text{black})$ is the colored ball in the container with the lowest closest number to $(9,\text{open})$. After this, there becomes 5 colored balls in the container: $(3,\text{red})$, $(6,\text{black})$, $(9,\text{black})$, $(12,\text{red})$, and $(14,\text{black})$. Next, if we put a $(10,\text{open})$ ball into the container, then it will shift its color into black because $(9,\text{black})$ is the colored ball in the container with the lowest closest number to $(10,\text{open})$. After this, there becomes 6 colored balls in the container: $(3,\text{red})$, $(6,\text{black})$, $(9,\text{black})$, $(10,\text{black})$, $(12,\text{red})$, and $(14,\text{black})$. In this example, the container ends up with 6 colored balls with 2 red balls and 4 black balls.

Notice that the final result might be different if we put the open-color balls in a different order. In the previous example, if we put $(10,\text{open})$ first before $(9,\text{open})$, then the container ends up with 4 red balls and 2 black balls.

Given $N$ colored balls in a container and $M$ open-color balls, your task in this problem is to determine the number of ways to put all open-color balls into the container such that the container ends up with strictly more red balls than black balls. Two ways are considered different if and only if there exists an $i$ such that the $i^\text{th}$ open-color ball put into the container is different. Note that you can only put the open-color balls into the container one by one.

Input Format

Input begins with a line containing two integers: $N\ M$ ($1 \leq N, M \leq 50$) representing the number of colored balls and the number of open-color balls, respectively. The next $N$ lines each contains an integer and a string: $A_i\ S_i$ ($0 \leq A_i \leq 10^9$; $S_i \in \{\text{RED}, \text{BLACK}\}$) representing the number and color of the $i^\text{th}$ ball, respectively. The next line contains $M$ integers: $B_i$ ($0 \leq B_i \leq 10^9$) representing the number of the open-color balls. It is guaranteed that there are no balls (both colored and open-color) which have the same number, i.e. $|A \cup B| = N + M$ where $A$ is the set of all unique numbers on the colored balls and $B$ is the set of all unique numbers on the open-color balls.

Output Format

Output in a line an integer representing the number of ways to put all the open-color balls into the container such that the container ends up with strictly more red balls than black balls, modulo $998\,244\,353$.

2 3
1 BLACK
10 RED
2 5 7

3

2 3
1 RED
10 BLACK
2 4 7

6

Hint

Explanation for the sample input/output #1

There are 3 ways to put all the open-color balls such that the container ends up with strictly more red balls than black balls.

• $(2,\text{open}), (7,\text{open}), (5,\text{open}) \rightarrow 3$ red and $2$ black balls
• $(7,\text{open}), (2,\text{open}), (5,\text{open}) \rightarrow 3$ red and $2$ black balls
• $(7,\text{open}), (5,\text{open}), (2,\text{open}) \rightarrow 3$ red and $2$ black balls

Explanation for the sample input/output #2

Regardless of how we put all the open-color balls, the container will always end up with more red balls than black balls.