Pokegene

친근한 포켓몬 박사인 오박사는 최근 포켓몬의 조상에 관한 질문을 많이 받고 있다.

많은 포켓몬 트레이너가 궁금해하는 것 중 하나는 자신의 포켓몬 도감에 있는 포켓몬들의 공통 조상을 찾는 것이다. 특히 각 트레이너는 자신이 가진 포켓몬 중 정확히 L마리의 조상인 포켓몬의 수를 알고 싶어한다. L의 값 또한 질문하는 트레이너가 정한다.

포켓몬 세계에서 포켓몬 A와 포켓몬 B의 유전자 문자열이 주어졌을 때, 포켓몬 A의 유전자 문자열이 포켓몬 B의 유전자 문자열의 접두사일 때 그리고 그럴 때만 포켓몬 A는 포켓몬 B의 조상이라고 한다. 또한 비어 있지 않은 모든 유전자 문자열은 포켓몬 세계의 실제 포켓몬에 대응한다.

오박사의 포켓몬 유전자 데이터베이스가 주어졌을 때, 트레이너들의 질문에 답하도록 도와주자.

입력의 첫째 줄에는 오박사의 데이터베이스에 있는 포켓몬의 수 N (1 ≤ N ≤ 200 000)과 오박사에게 질문이 있는 포켓몬 트레이너의 수 Q (1 ≤ Q ≤ 200 000)가 주어진다. 다음 N개의 줄에는 오박사의 데이터베이스에 있는 포켓몬 유전자 문자열이 하나씩 주어진다. 모든 유전자 문자열은 서로 다르며 알파벳 소문자로 이루어져 있다.

그다음 2 · Q개의 줄이 주어진다. 각 포켓몬 트레이너의 질문은 두 줄로 이루어진다. 각 질문의 첫째 줄에는 트레이너가 소유한 포켓몬의 수 K (1 ≤ K ≤ N)와 문제에서 설명한 값 L (1 ≤ L ≤ K)이 주어진다. 둘째 줄에는 서로 다른 K개의 정수가 공백으로 구분되어 주어진다. K개의 정수 목록에서 정수 x는 이 트레이너가 오박사의 데이터베이스에 있는 x번째 포켓몬을 소유하고 있음을 나타내며, 오박사가 소유한 포켓몬은 1번부터 N번까지 번호가 매겨져 있다.

입력에서 유전자 문자열 길이의 합은 200 000자를 넘지 않고, 모든 질문에서 K의 합은 1 000 000을 넘지 않는다.

각 포켓몬 트레이너의 질문에 대해, 그 트레이너가 소유한 K마리의 포켓몬 중 정확히 L마리의 조상인 포켓몬의 수를 출력한다. 비어 있지 않은 모든 유전자 문자열은 포켓몬에 대응한다고 가정한다. L은 질문에서 정의되며 모든 질문에서 같을 필요는 없다.

오박사의 데이터베이스에는 다섯 마리의 포켓몬 “nib”, “abcd”, “abee”, “abced”, “nit”이 있다. 질문을 하는 트레이너는 두 명이다.

첫 번째 포켓몬 트레이너는 유전자 문자열이 “nib”, “abcd”, “nit”, “abee”인 포켓몬을 소유하고 있으며, 자신의 포켓몬 중 정확히 두 마리의 조상인 포켓몬이 몇 마리인지 알고 싶어한다. 유전자 문자열이 “a”와 “ab”인 포켓몬은 “abcd”와 “abee”의 조상이고, 유전자 문자열이 “n”과 “ni”인 포켓몬은 “nib”와 “nit”의 조상이므로 답은 4이다.

두 번째 포켓몬 트레이너는 유전자 문자열이 “abcd”, “abee”, “abced”인 포켓몬을 소유하고 있으며, 마찬가지로 자신의 포켓몬 중 정확히 두 마리의 조상인 포켓몬이 몇 마리인지 알고 싶어한다. 유전자 문자열이 “abc”인 포켓몬만이 소유한 포켓몬 “abcd”와 “abced” 정확히 2마리의 조상이므로 답은 1이다.