У Фермера Джона есть \(N\) подарков помеченных числами \(1\ldots N\) для его
\(N\) коров, также помеченных числами \(1\ldots N\) (\(1\le N\le 18\))
Каждая корова имеет список предпочтений, который представляет собой
перестановку из всех \(N\) подарков, так что корова предпочитает подарок,
который появился в списке раньше подарку, который появился в списке позже.
ФД по лени просто назначил корове \(i\) подарок \(i\) для всех \(i\).
Теперь коровы собрались и решили переназначить подарки так, чтобы у каждой
коровы либо остался изначальный подарок, либо он был заменён на более
предпочитаемый подарок.
Имеется также дополнительное ограничение: подарок может быть переназначен
корове, если он изначально был назначен корове такого же типа (Holstein или
Guernsey)). Задано \(Q\) (\(1\le Q\le \min(10^5,2^N)\))длин \(N\) строк пород
для каждой из них вычислите количество переназначений, соответствующих ей.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\).
Каждая из следующих \(N\) строк содержит список предпочтений одной коровы.
Гарантируется, что каждая строка является перестановкой \(1\dots N\).
Следующая строка содержит \(Q\).
Каждая из последующих \(Q\) строк содержит строку пород, каждая имеет \(N\)
символов длину и состоит только из символов G и H. Никакая из строк пород
не появится более одного раза.
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждой строки пород выведите количество перестановок, соответствующих ей
на отдельной строке.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|