Valid Gift Reassignment

Farmer John has \(N\) gifts labeled \(1,2,\dots,N\) for his \(N\) cows also labeled \(1,2,\dots,N\) (\(1\le N\le 18\)). Each cow has a wishlist which is a permutation of \(\{1,2,\dots,N\}\). In a wishlist, a cow prefers the gifts which appear earlier over those that appear later. Initially, Farmer John assigns gift \(i\) to cow \(i\). The cows now decide to reassign the gifts among themselves subject to the following conditions:

• After reassignment, every cow ends up with either the same gift as originally assigned or a gift she prefers over the one she was originally given. Formally, if the wishlist of cow \(i\) is denoted by a permutation \(L_i\) (with \(L_i(0)\) being the most preferred), and if gift \(i\) appears at position \(p_i\) in \(L_i\), then cow \(i\) may only receive a gift \(j\) if the position of \(j\) in \(L_i\) is at most \(p_i\) (i.e. \(\mathrm{pos}_{L_i}(j)\leq \mathrm{pos}_{L_i}(i)\)).
• A gift originally assigned to a cow of a certain breed may only be reassigned to a cow of the same breed. Each cow is either a Holstein (H) or a Guernsey (G). In other words, if in the breed string the \(i\)th character denotes the type of cow \(i\), then cow \(i\) can only receive a gift \(j\) if the breed of cow \(i\) is the same as the breed of cow \(j\) (since gift \(j\) was originally given to cow \(j\)).

You are given the wishlists for all \(N\) cows followed by \(Q\) breed strings. For each breed string, compute the number of gift reassignments that satisfy the given conditions. \(Q\) satisfies \(1\le Q\le\min(10^5,2^N)\).

inputFormat

The input begins with an integer \(N\) (\(1\le N\le 18\)). Following this are \(N\) lines. The \(i\)th of these lines contains a permutation of \(1,2,\dots, N\) representing the wishlist of cow \(i\) (from most to least preferred).

The next line contains an integer \(Q\) (\(1\le Q\le \min(10^5,2^N)\)). Each of the following \(Q\) lines contains a string of length \(N\) consisting only of characters 'H' and 'G', which denotes the breed of each cow (in order from cow 1 to cow \(N\)).

outputFormat

For each query, output a single integer denoting the number of valid gift reassignments. Each answer should be printed on a new line.

sample

3
1 2 3
2 1 3
1 3 2
2
HHH
HGH

1
1