Phân Phối Quà Tặng (Gold)

Farmer John có $N$ món quà (đánh số từ $1$ đến $N$) cho $N$ con bò (đánh số từ $1$ đến $N$). Mỗi con bò có một danh sách ưu tiên, là hoán vị của $N$ món quà. Ban đầu, quà $i$ được trao cho bò $i$.

Các con bò có thể trao đổi quà với điều kiện: mỗi con bò phải nhận được cùng món quà ban đầu hoặc một món quà ưa thích hơn.

Tuy nhiên, mỗi con bò thuộc một trong hai giống: Holstein (H) hoặc Guernsey (G). Một món quà chỉ có thể được trao cho con bò cùng giống với con bò ban đầu nhận nó.

Cho $Q$ truy vấn, mỗi truy vấn chỉ định giống của từng con bò. Với mỗi truy vấn, đếm số cách phân phối quà hợp lệ.

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• $N$ dòng tiếp theo: Danh sách ưu tiên của bò $i$
• Dòng $N+2$: Số nguyên $Q$
• $Q$ dòng tiếp theo: Xâu ký tự 'G' và 'H' độ dài $N$, chỉ định giống của mỗi con bò

Dữ liệu ra

• $Q$ dòng, mỗi dòng là số cách phân phối hợp lệ cho truy vấn tương ứng.

Ràng buộc

• $1\le N\le 18$
• $1\le Q\le min({10}^5,2^N)$

Ví dụ