겹치지 않는 등장 위치

문자열 $s$에서 문자열 $t$의 겹치지 않는 등장 위치 집합이란, $t$가 $s$에 등장하는 위치들의 집합으로서 어느 두 등장 위치도 서로 겹치지 않는 것을 말한다. 즉, $s$의 어떤 문자 위치도 두 개의 서로 다른 등장 위치에 속하지 않는다.

소문자 영어 알파벳 $n$개로 이루어진 문자열 $s$와 $m$개의 질의가 주어진다. 각 질의는 문자열 $t\_i$ 하나로 이루어진다.

각 질의마다, $s$에서 $t$의 겹치지 않는 등장 위치 집합의 최대 크기를 출력한다.

첫째 줄에 문자열 $s$의 길이 $n$과 질의의 개수 $m$이 공백으로 구분되어 주어진다 ($1 \le n \le 10^{5}$, $1 \le m \le 10^{5}$).

둘째 줄에 소문자 영어 알파벳 $n$개로 이루어진 문자열 $s$가 주어진다.

다음 $m$개의 줄에 각각 소문자 영어 알파벳으로 이루어진 문자열 $t\_i$가 주어진다. 이는 $i$번째 질의이다 ($1 \le |t\_i| \le n$이며, $|t\_i|$는 문자열 $t\_i$의 길이이다).

모든 $t\_i$의 길이의 합은 $10^{5}$ 이하임이 보장된다.

각 질의 $i$마다 $s$에서 $t\_i$의 겹치지 않는 등장 위치 집합의 최대 크기를 한 줄에 하나씩 출력한다.