Farmer John có \(N\) món quà được đánh số \(1\ldots N\) dành cho \(N\) con bò cũng được đánh số \(1\ldots N\) (\(1\le N\le 18\)). Mỗi con bò có một danh sách mong muốn là một hoán vị của toàn bộ \(N\) món quà; con bò thích những món xuất hiện sớm hơn trong danh sách hơn những món xuất hiện muộn hơn.

FJ đã lười biếng và chỉ gán quà \(i\) cho bò \(i\) với mọi \(i\). Giờ đây, đàn bò đã tụ họp và quyết định phân phối lại các món quà sao cho sau khi phân phối lại, mỗi con bò nhận được chính món quà ban đầu của mình hoặc một món mà nó thích hơn món ban đầu.

Còn có một ràng buộc bổ sung: một món quà chỉ được phân phối lại cho một con bò nếu ban đầu nó được gán cho một con bò cùng giống (mỗi con bò là Holstein hoặc Guernsey). Cho \(Q\) (\(1\le Q\le\min(10^5,2^N)\)) chuỗi giống độ dài \(N\), với mỗi chuỗi hãy đếm số cách phân phối lại phù hợp với chuỗi đó.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa danh sách ưu tiên của một con bò. Bảo đảm rằng mỗi dòng là một hoán vị của \(1\dots N\).

Dòng tiếp theo chứa \(Q\).

\(Q\) dòng cuối, mỗi dòng chứa một chuỗi giống dài \(N\) ký tự và chỉ gồm các ký tự G và H. Không có chuỗi giống nào xuất hiện nhiều hơn một lần.

Dữ liệu ra

Với mỗi chuỗi giống, in trên một dòng mới số cách phân phối lại phù hợp với chuỗi đó.

Phân nhóm

• Với \(T=2,\ldots,13\), test \(T\) thỏa mãn \(N=T+4\).
• Các test 14–18 thỏa mãn \(N=18\).

Ví dụ

4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
HHHH
HHGG
GHGH
HGGG
GHHG

2
1
1
2
2

Nguồn

USACO 2022 February Contest, Gold — Redistributing Gifts: https://usaco.org/index.php?page=viewproblem2&cpid=1209

Tác giả: Benjamin Qi.