합자

Vivi는 폰트 디자이너로 일한다. 새 작품을 거의 완성했지만 무언가 빠졌다고 생각해서 합자(ligature)를 몇 개 추가하기로 했다. 합자는 두 글자가 하나의 글리프로 합쳐진 것이다. 예를 들어 "ff"는 자주 "ff"이 되고, 옛 라틴어 글에서는 "ae"가 "æ"가 되기도 했다.

Vivi는 알맞은 합자를 고르는 일이 중요하다는 것을 안다. 운이 좋으면 그녀의 합자도 라틴어 "et"(뜻은 "and")에서 온 합자 "&"만큼 오래 쓰일지도 모른다! 합자는 보통 자주 나오는 글자 쌍에서 고른다. 좋은 집합은 합자 종류가 너무 많지 않으면서도 많이 나타나게 한다.

Vivi는 이 일을 진지하게 여겨 합자 집합 후보 $Q$개를 만들었다. 각 집합에는 합자가 $K$개씩 들어 있다. 이제 각 후보를 코퍼스에 적용해서 합자가 몇 번 나타나는지 세어 달라고 한다.

코퍼스는 왼쪽에서 오른쪽으로 읽으며, 합자끼리는 다시 합칠 수 없다. "ab", "bc", "cd"에 합자가 있으면 "abcd"는 "ab"와 "cd" 두 개의 합자를 가진 것으로 센다.

첫 줄에는 세 정수 $N$(코퍼스의 길이, $1 \le N \le 10^6$), $Q$(후보의 수, $1 \le Q \le 10^5$), $K$(각 집합의 합자 수, $1 \le K \le 20$)가 주어진다.

둘째 줄에는 a-z로 이루어진 길이 $N$의 코퍼스 문자열이 주어진다.

이어서 $Q$개의 줄에 각각 $2K$개의 문자로 된 합자 후보가 주어진다. 처음 두 문자가 첫 번째 합자, 다음 두 문자가 두 번째 합자를 이루며, 이런 식으로 이어진다. 한 후보 안에서 같은 글자 쌍이 두 번 나오는 일은 없다.

각 합자 집합마다 한 줄에 코퍼스를 왼쪽에서 오른쪽으로 읽고 주어진 합자를 적용했을 때의 합자 출현 횟수를 출력한다.

세 예제는 처음 세 개의 서브태스크에 해당한다.

첫 번째 예제의 첫 번째 질문에서 합자 "aa"는 "ababbab aa ba aa b aa aa"처럼 나타나며, 4번 출현한다.

두 번째 예제의 첫 번째 질문에는 합자 "aa"와 "ab"가 있다. 코퍼스를 왼쪽에서 오른쪽으로 읽으면 8번 출현한다: "bc ab ab b ab aa b aa ab aa aa".