bronze_Hoof_Paper_Scissors_Minus_One (USACO US_Open_Contest)
Time limit: 3 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: implementation, bitmask

**Note: The time limit for this problem is 3s, 1.5x the default.**
In a game of Hoof Paper Scissors, Bessie and Elsie can put out one of $N$
($1 \leq N \leq 3000$) different hoof symbols labeled $1\dots N$, each
corresponding to a different material. There is a complicated chart of how the
different materials interact with one another, and based on that chart, either:
One symbol wins and the other loses.
The symbols draw against each other.
Hoof Paper Scissors Minus One works similarly, except Bessie and Elsie can each
put out two symbols, one with each hoof. After observing all four symbols that
they have all put out, they each choose one of their two symbols to play.  The
outcome is decided based on normal Hoof Paper Scissor conventions.
Given the $M$ ($1 \leq M \leq 3000$) symbol combinations that Elsie plans to
make across each game, Bessie wants to know how many different symbol
combinations would result in a guaranteed win against Elsie. A symbol
combination is defined as an ordered pair $(L,R)$ where $L$ is the symbol the
cow plays with her left hoof and $R$ is the symbol the cow plays with her right
hoof. Can you compute this for each game?
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains two space-separated integers $N$ and $M$ representing
the number of hoof symbols and the number of games that Bessie and Elsie play.
Out of the following $N$ lines of input, the $i$th line consists of $i$
characters  $a_{i,1}a_{i,2}\ldots a_{i,i}$ where each
$a_{i,j} \in \{\texttt D,\texttt W,\texttt L\}$. If $a_{i,j} = \texttt D$, then
symbol $i$ draws against symbol $j$.  If $a_{i,j} = \texttt W$, then symbol $i$
wins against symbol $j$. If $a_{i,j} = \texttt L$, then symbol $i$ loses against
symbol $j$. It is guaranteed that $a_{i,i} = \texttt D$.
The next $M$ lines contain two space separated integers $s_1$ and $s_2$ where
$1 \leq s_1,s_2 \leq N$. This represents Elsie's symbol combination for that
game.
OUTPUT FORMAT (print output to the terminal / stdout):
Output $M$ lines where the $i$-th line contains the number of symbol
combinations guaranteeing that Bessie can beat Elsie in the $i$-th game.
SAMPLE INPUT:
3 3
D
WD
LWD
1 2
2 3
1 1
SAMPLE OUTPUT:
0
0
5
In this example, this corresponds to the
original Hoof Paper
Scissors
and we can let Hoof=1, Paper=2, and Scissors=3. Paper beats Hoof,
Hoof beats Scissors, and Scissors beats Paper. There is no way for Bessie to
guarantee a win against the combinations of Hoof+Paper or Paper+Scissors.
However, if Elsie plays Hoof+Hoof, Bessie can counteract with any of the
following combinations.
Paper+Paper
Paper+Scissors
Paper+Hoof
Hoof+Paper
Scissors+Paper
If Bessie plays any of these combinations, she can guarantee that she wins by
putting forward Paper.
SCORING:
Inputs 2-6: $N,M\le 100$
Inputs 7-12: No additional
constraints.
Problem credits: Suhas Nagar

Starter code:

Grader code:

Setup script:

Evaluation script: