Page not loading? Try clicking here.
Placeholder

#8412

Hoof Paper Scissors Minus One 3s 1024MB

Problems

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

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 ith 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

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.


Example 

3 3
D
WD
LWD
1 2
2 3
1 1
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.



Source

USACO 2025 US Open Bronze

You must sign in to write code.