문제
포켓몬 전공의 친근한 인상을 가진 Oak 교수는 지금까지도 포켓몬의 조상에 대한 많은 질문을 고민해 왔다.
많은 포켓몬 트레이너가 심각하게 생각하는 것 중 하나는 자신의 포켓몬 도감에 있는 포켓몬들의 공통 조상을 찾는 것이다. 자세하게는, 각 포켓몬 트레이너는 “자신이 가진 포켓몬 중 정확히 L마리에게만 조상이 되는” 포켓몬의 수를 알고 싶어 한다. L의 값은, 물론, 질문하는 트레이너가 결정하는 값이다.
포켓몬 월드에서, 포켓몬 A와 포켓몬 B의 유전자가 주어졌을 때, 포켓몬 A가 포켓몬 B의 조상인 것과 포켓몬 A의 유전자가 포켓몬 B의 유전자의 접두사인 것은 동치이다. 또한, 모든 빈 문자열이 아닌 유전자 문자열에 대해, 각 유전자를 가진 포켓몬은 포켓몬 월드에 항상 존재한다.
Oak 교수의 포켓몬 유전자 데이터베이스가 주어졌을 때, 트레이너의 질문에 답해주자.
입력
첫 번째 줄에 Oak 교수의 데이터베이스에 있는 포켓몬의 수 N과, 트레이너의 질문 수 Q가 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ Q ≤ 200,000)
다음 N개의 줄에는 Oak 교수의 데이터베이스에 있는 포켓몬들의 유전자 정보가 알파벳 소문자로 이루어진 문자열로 주어진다.
다음 2Q개의 줄에는 각 질문이 2개의 줄 단위로 주어진다. 첫 번째 줄에는 트레이너가 가지고 있는 포켓몬의 수 K와, 질문에서 결정되는 값인 L이 주어진다. (1 ≤ L ≤ K ≤ N) 두 번째 줄에는 트레이너가 가지고 있는 포켓몬에 대한 정보가 공백으로 구분 된 K개의 정수로 주어진다.
유전자 길이의 총합은 200,000을 넘지 않으며, 모든 질문에 대한 K의 합은 1,000,000을 넘지 않는다.
출력
각 포켓몬 트레이너의 질문에 대해, “자신이 가진 포켓몬 중 정확히 L마리에게만 조상이 되는” 포켓몬의 수를 출력한다.
예제
5 2
nib
abcd
abee
abced
nit
4 2
1 2 5 3
3 2
2 3 4
4
1
Oak 교수의 데이터베이스에는 5마리의 포켓몬이 있다: “nib”, “abcd”, “abee”, “abced”, 그리고 “nit”. 트레이너에게는 2개의 질문이 있다.
첫 번째 포켓몬 트레이너는 “nib”, “abcd”, “nit”, 그리고 “abee”가 있으며, 자신의 포켓몬들 중 정확히 둘에게만 조상이 되는 포켓몬의 수를 알고 싶어 한다. 유전자가 “a”와 “ab”인 포켓몬은 “abcd”, “abee”의 조상이고, 유전자가 “n”와 “ni”인 포켓몬은 “nib”, “nit”의 조상이므로 4마리가 존재한다.
두 번째 포켓몬 트레이너는 “abcd”, “abee”, 그리고 “abced”가 있으며, 자신의 포켓몬들 중 정확히 둘에게만 조상이 되는 포켓몬의 수를 알고 싶어 한다. 유전자가 “abc”인 포켓몬은 “abcd”, “abced”의 조상이므로, 답은 1이다.
로그인해야 코드를 작성할 수 있어요.