**Замечание Время на тест для этой задачи 3сек, в 1.5 раза больше чем по умолчанию.**
В игре "Камень, ножницы бумага" Беси и Эльза могут положить один из
\(N\) (\(1 \leq N \leq 3000\)) различных символов, обозначенных от
\(1\dots N\), каждый соответствует различному материалу.
В этой игре усложнённый алгоритм взаимодействия различных материалов
друг с другом, как описывается далее.
- Один символ побеждает, все другие проигрывают.
- Эти другие символы играют вничью друг с другом.
"Камень, ножницы, бумага минус один" играются аналогично за исключением того,
что Беси и Эльза могут выбрать два символа. После анализа всех четырёх
символов, которые они выбрали, они могут выбрать один из их двух символов к игре.
Результат определяется по обычным правилам.
Вам даны \(M\) (\(1 \leq M \leq 3000\)) комбинаций символов, которые Эльза планирует
использовать в каждой игре. Беси хочет узнать, сколько различных комбинаций символов
гарантируют, что она победит Эльзу. Комбинация символов определяется как упорядоченная
пара \((L,R)\), где \(L\) - символ, которым корова играет левым копытом, а \(R\) - символ
которым играет корова правым копытом. Вы можете это вычислить для каждой игры.
ФОРМАТ ВВОДА (с клавиатуры / stdin) :
Первая строка содержит два разделённых одиночным пробелом целых числа
\(N\) и
\(M\),
представляющих количество символов камней и количество игр, которые будут играть
Беси и Эльза.
Из последующих \(N\) строк ввода \(i\)-ая строка состоит из \(i\) символов
\(a_{i,1}a_{i,2}\ldots a_{i,i}\) где каждый
\(a_{i,j} \in \{\texttt D,\texttt W,\texttt L\}\).
Если \(a_{i,j} = \texttt D\), тогда символ \(i\) играет вничью с символом \(j\).
Если \(a_{i,j} = \texttt W\), тогда символ \(i\) выигрывает у символа \(j\).
Если \(a_{i,j} = \texttt L\), тогда символ \(i\) проигрывает символу \(j\).
Гарантируется, что \(a_{i,i} = \texttt D\).
Следующие \(M\) строк содержат два разделённых пробелом целых числа \(s_1\) и \(s_2\)
где \(1 \leq s_1,s_2 \leq N\). Они представляют комбинацию Эльзы для игры.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(M\) строк, где \(i\)-ая строка содержит количество комбинаций символов,
гарантирующих победу Беси над Эльзой в \(i\)-ой игре.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
D
WD
LWD
1 2
2 3
1 1
|
0
0
5
|