33998번 - 거의 같은 문자열

문제

알파벳 소문자로 이루어진 문자열 $S$에 대한 쿼리가 총 $M$개 주어진다. 매 쿼리는 문자열 $Q_i$로 이루어져 있다. 각각의 쿼리에 대해서 다음을 구해보자.

• $S$의 연속 부분 문자열 중에서 $Q_i$와 거의 같은 문자열의 개수를 출력한다.

여기서 두 문자열이 거의 같다라는 것은 두 문자열을 정렬했을 때 같은 문자열을 말한다.

예를 들어 문자열 cba, bac는 두 문자열은 정렬했을 때 abc로 동일하여 거의 같은 문자열이다.

입력

첫째 줄에 정수 $N$과 $M$이 공백으로 구분되어 주어진다. $(1\leq N, M\leq 10^5)$

둘째 줄에 알파벳 소문자로 이루어진 길이 $N$의 문자열 $S$가 주어진다.

셋째 줄부터 $M$개의 줄에 걸쳐 문자열 $Q_i$가 주어진다. $(1 \leq i \leq M; \sum_{i=1}^{M} |Q_i| \leq 10^5)$

출력

쿼리가 주어질 때마다 한 줄에 하나씩 정답을 출력한다.

제한

힌트