Lưu ý: Giới hạn thời gian của bài này là 3 giây, bằng 1,5 lần giới hạn mặc định.

Trong một ván Hoof Paper Scissors, Bessie và Elsie có thể đưa ra một trong \(N\) (\(1 \leq N \leq 3000\)) ký hiệu móng khác nhau, được đánh số từ \(1\) đến \(N\), mỗi ký hiệu tương ứng với một vật liệu khác nhau. Có một bảng phức tạp mô tả cách các vật liệu tương tác với nhau; dựa trên bảng đó, một trong hai trường hợp sau xảy ra:

• Một ký hiệu thắng và ký hiệu còn lại thua.
• Hai ký hiệu hòa nhau.

Hoof Paper Scissors Minus One cũng tương tự, ngoại trừ Bessie và Elsie mỗi cô có thể đưa ra hai ký hiệu, mỗi móng một ký hiệu. Sau khi quan sát cả bốn ký hiệu đã được đưa ra, mỗi cô chọn một trong hai ký hiệu của mình để chơi. Kết quả được quyết định theo quy tắc Hoof Paper Scissors thông thường.

Biết \(M\) (\(1 \leq M \leq 3000\)) tổ hợp ký hiệu mà Elsie dự định sử dụng trong từng ván, Bessie muốn biết có bao nhiêu tổ hợp ký hiệu khác nhau giúp cô chắc chắn thắng Elsie. Một tổ hợp ký hiệu được định nghĩa là một cặp có thứ tự \((L,R)\), trong đó \(L\) là ký hiệu con bò đưa ra bằng móng trái và \(R\) là ký hiệu con bò đưa ra bằng móng phải. Hãy tính kết quả cho từng ván.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách \(N\) và \(M\), lần lượt là số ký hiệu móng và số ván mà Bessie và Elsie chơi.

Trong \(N\) dòng tiếp theo, dòng thứ \(i\) gồm \(i\) ký tự \(a_{i,1}a_{i,2}\ldots a_{i,i}\), với mỗi \(a_{i,j} \in \{\texttt D,\texttt W,\texttt L\}\). Nếu \(a_{i,j}=\texttt D\), ký hiệu \(i\) hòa ký hiệu \(j\). Nếu \(a_{i,j}=\texttt W\), ký hiệu \(i\) thắng ký hiệu \(j\). Nếu \(a_{i,j}=\texttt L\), ký hiệu \(i\) thua ký hiệu \(j\). Đảm bảo \(a_{i,i}=\texttt D\).

\(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(s_1\) và \(s_2\), với \(1 \leq s_1,s_2 \leq N\). Đây là tổ hợp ký hiệu của Elsie trong ván tương ứng.

Dữ liệu ra

In ra \(M\) dòng, dòng thứ \(i\) chứa số tổ hợp ký hiệu đảm bảo Bessie có thể thắng Elsie trong ván thứ \(i\).

Ví dụ

3 3
D
WD
LWD
1 2
2 3
1 1

0
0
5

Phân nhóm

• Dữ liệu 2–6: \(N,M\le 100\).
• Dữ liệu 7–12: Không có ràng buộc bổ sung.

Đề bài: Suhas Nagar.

Nguồn

USACO 2025 US Open Contest, Bronze — Hoof Paper Scissors Minus One: https://usaco.org/index.php?page=viewproblem2&cpid=1515