Її перше ім'я

У королівській родині імена мають велике значення! Вам, як королівському історику, доручено дослідити закономірності в іменах королівських дам королівства.

Усього є $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\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 p_i<i$ для $i>1)$ — номер її матері (або $0$, у випадку Першої леді). Усі імена унікальні.

Решта $k$ рядків містять по одному непорожньому рядку запиту, що складається тільки з великих літер. Сума довжин рядків запиту не перевищує $10^6$.

Вихідні дані

Виведіть $k$ рядків, де $i$-й рядок містить кількість королівських дам, у яких $i$-й рядок запиту є префіксом їхнього імені.

Приклади