В королевской семье имена очень важны! Вам как королевскому историку поручено проанализировать закономерности в именах королевских дам королевства. Всего имеется $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 не является префиксом имени какой-либо королевской леди. \InputFile В первой строке записаны два целых числа $n$ и $k$, где $n~(1 \le n \le 10^6)$ --- общее количество королевских дам, а $k~(1 \le k \le 10^ 6)$ --- количество строк запроса. Затем следуют $n$ строк, описывающих королевских дам. $i$-я из этих строк описывает королевскую даму с номером $i$ и содержит прописную букву $c_i$ ('A' --- 'Z') и целое число $p_i$, где $c_i$ --- первая буква имени леди $i$, а $p_i~(p_1 = 0$ и $1 \le pi < i$ для $i > 1)$ --- номер ее матери (или $0$, в случае Первой леди). Все имена уникальны. Остальные $k$ строк содержат по одной непустой строке запроса, состоящей только из заглавных букв. Сумма длин строк запроса не превышает $10^6$. \OutputFile Выведите $k$ строк, где $i$-я строка содержит количество королевских дам, у которых $i$-я строка запроса является префиксом их имени.