Її перше ім'я#11350
У королівській родині імена мають велике значення! Вам, як королівському історику, доручено дослідити закономірності в іменах королівських дам королівства.
Усього є королівських дам, пронумерованих для зручності від до . Ім'я кожної леді складається з великої літери, з'єднаної з ім'ям її матері. Виняток становить леді з номером , засновниця королівської родини, ім'я якої складається лише з однієї великої літери.
Наприклад, ENERYS може бути матір'ю AENERYS (оскільки ім'я AENERYS складається з великої літери ‘A’, з'єднаної з ENERYS, яка є ім'ям її матері). Так само AENERYS могла бути матір'ю DAENERYS і YAENERYS.
Вам надано опис усіх королівських дам. Ваше завдання — для деяких цікавих рядків визначити кількість королівських дам, для яких є префіксом імені. Наприклад, розглянемо приклад вхідних даних 1 нижче, де королівська лінія йде прямо від засновника S до AENERYS (через YS, RYS, ERYS, NERYS і ENERYS), при цьому у кожної леді є рівно одна дочка. Потім у AENERYS є дві дочки — DAENERYS і YAENERYS, причому у останньої є одна дочка, RYAENERYS.
У такій родині RY є префіксом імен двох дам: RYS і RYAENERYS. E — префікс імен ERYS і ENERYS. N — це префікс тільки імені NERYS, тоді як S — це префікс тільки імені засновника S. AY не є префіксом імені жодної королівської леді.
У першому рядку записані два цілі числа і , де n~(1 \le n \le 10^6) — загальна кількість королівських дам, а k~(1 \le k \le 10^6) — кількість рядків запиту.
Далі йдуть рядків, що описують королівських дам. -й з цих рядків описує королівську даму з номером і містить велику літеру c_i ('A' — 'Z') та ціле число p_i, де c_i — перша літера імені леді , а p_i~(p_1 = 0 і 1 \le p_i < i для i > 1) — номер її матері (або , у випадку Першої леді). Усі імена унікальні.
Решта рядків містять по одному непорожньому рядку запиту, що складається тільки з великих літер. Сума довжин рядків запиту не перевищує 10^6.
Виведіть рядків, де -й рядок містить кількість королівських дам, у яких -й рядок запиту є префіксом їхнього імені.
Приклад 1