Выбор книг из каталога выдач

В библиотечном каталоге каждая строка описывает один экземпляр книги. Экземпляр со статусом ON_SHELF находится на полке и может быть включён в тематическую подборку. Экземпляры со статусами ISSUED и UNKNOWN в подборку не включаются.

Для каждого запроса задано число k — требуемое количество книг в подборке. Порядок выбора книг не важен: набор из книг A и B совпадает с набором из книг B и A.

Пусть m — количество строк каталога со статусом ON_SHELF. Для каждого запроса необходимо вывести число способов выбрать ровно k экземпляров книг. Требуется вычислить число сочетаний: C(m, k) = m! / (k! · (m-k)!) при 0 ≤ k ≤ m; если k > m, ответ равен 0. По определению C(0, 0) = 1.

Если инвентарные коды в нескольких строках совпадают, строки всё равно считаются разными экземплярами книг.

Формат ввода

В первой строке дано целое число n — число строк каталога.

В следующих n строках записаны инвентарный код и статус экземпляра через пробел.

Затем дано целое число q — число запросов.

В следующих q строках дано по одному целому числу k — размер требуемой подборки.

Формат вывода

Выведите q целых чисел: по одному ответу для каждого запроса в том же порядке.

Выведите целое число без округления, дробная часть отсутствует.

Ограничения

1 ≤ n ≤ 1000.

Длина каждого инвентарного кода составляет от 1 до 20 символов. Код состоит из латинских букв, цифр и символа _.

Статус каждой строки равен одному из значений: ON_SHELF, ISSUED, UNKNOWN.

1 ≤ q ≤ 1000.

0 ≤ k ≤ 1000.