이름의 시작

왕실에서 이름은 매우 중요하다. 왕실 역사가인 당신은 왕국 왕실 부인들의 이름에 나타나는 규칙을 분석하는 임무를 맡았다.

왕실 부인은 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이며, 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이며 i > 1일 때 1 ≤ pi < i)는 어머니의 번호이다(첫 번째 부인의 경우 0). 모든 이름은 서로 다르다.

남은 k개의 줄에는 각각 알파벳 대문자로만 이루어진, 비어 있지 않은 질의 문자열이 하나씩 주어진다. 질의 문자열 길이의 합은 106 이하이다.

k개의 줄을 출력한다. i번째 줄에는 i번째 질의 문자열을 이름의 접두사로 가지는 왕실 부인의 수를 출력한다.