В королевской семье имена очень важны! Вам как королевскому историку поручено проанализировать закономерности в именах королевских дам королевства.
Всего имеется n королевских дам, для удобства пронумерованных от 1 до n. Имя каждой леди представляет собой заглавную букву, соединенную с именем ее матери. Исключение составляет леди с номером 1, основательница королевской семьи, имя которой состоит всего из одной заглавной буквы.
Например, ENERYS может быть матерью AENERYS (поскольку имя AENERYS состоит из единственной заглавной буквы ‘A’, соединенной с ENERYS, которая является именем ее матери). Точно так же AENERYS могла быть матерью DAENERYS и YAENERYS.
Вам дано описание всех королевских дам. Ваша задача — по некоторым интересным строкам s определить количество королевских дам, для которых s является префиксом имени. Например, рассмотрим пример входных данных 1 ниже, где королевская линия идет прямо от основателя S к AENERYS (через YS, RYS, ERYS, NERYS и ENERYS), при этом у каждой леди есть ровно одна дочь. Затем у AENERYS есть две дочери — DAENERYS и YAENERYS, причем у последней есть одна дочь, RYAENERYS.
В такой семье RY является префиксом имен двух дам: RYS и RYAENERYS. E — префикс имен ERYS и ENERYS. N — это префикс только имени NERYS, тогда как S — это префикс только имени основателя S. AY не является префиксом имени какой-либо королевской леди.
В первой строке записаны два целых числа n и k, где n (1≤n≤106) — общее количество королевских дам, а k (1≤k≤106) — количество строк запроса.
Затем следуют n строк, описывающих королевских дам. i-я из этих строк описывает королевскую даму с номером i и содержит прописную букву ci ('A' — 'Z') и целое число pi, где ci — первая буква имени леди i, а pi (p1=0 и 1≤pi<i для i>1) — номер ее матери (или 0, в случае Первой леди). Все имена уникальны.
Остальные k строк содержат по одной непустой строке запроса, состоящей только из заглавных букв. Сумма длин строк запроса не превышает 106.
Выведите k строк, где i-я строка содержит количество королевских дам, у которых i-я строка запроса является префиксом их имени.