고급 레스토랑

상근이는 고급 레스토랑을 운영한다. 원자력 발전소 사고 이후로 사람들이 방사능을 크게 두려워하게 되자, 정부는 $M$종류의 재료에 든 방사능이 위험한 수준이라고 판단하고 이 재료를 요리에 조금도 쓰지 못하게 하는 법을 만들었다.

모든 재료에는 0부터 9까지의 숫자로만 이루어진 시리얼 번호가 붙어 있다. 상근이의 레스토랑은 음식을 한 가지만 만들고, 상근이는 그 음식에 들어가는 재료의 시리얼 번호를 모두 알고 있다.

상근이는 재료마다 방사능에 오염되었는지 확인해야 한다. 그런데 상근이는 몹시 게을러서, 요리에 들어가는 재료의 시리얼 번호를 순서대로 이어 붙여 길이가 $N$인 문자열 $A$를 만든 다음, 금지된 시리얼 번호가 $A$ 안에 들어 있는지만 검사하려고 한다.

근처에서 음식점을 하는 선영이는 로봇으로 이 검사를 자동으로 한다. 상근이는 선영이에게 부탁해 로봇을 빌려 왔다.

로봇은 시리얼 번호 $A$ 안에 시리얼 번호 $B$가 들어 있는지 다음 순서로 검사한다. $B$의 길이는 $L$이다.

• $A$의 1번째 숫자부터 $L$번째 숫자까지를 잘라 $B$와 앞에서부터 한 자리씩 비교한다. 서로 다른 숫자를 만나거나 마지막 자리까지 비교하면 비교를 멈춘다. 두 문자열이 같으면 성공 알림을 띄우고 검사를 끝낸다.
• 검사가 끝나지 않았으면 2번째 숫자부터 $L+1$번째 숫자까지를 같은 방식으로 비교한다. 그래도 같지 않으면 3번째부터 $L+2$번째까지, 4번째부터 $L+3$번째까지와 같은 순서로 검사를 이어 간다.
• 잘라낸 부분 문자열의 길이가 $L$보다 짧은 경우도 있다. ($A$의 길이가 8인데 5번째 자리부터 검사를 시작하는 경우) 이때는 뒤에 #을 붙여 길이를 $L$로 맞춘 다음 비교한다. 예를 들어 563232의 4번째 자리부터 10번째 자리까지는 232####이다. #은 0부터 9까지 어떤 숫자와도 같지 않다.
• 시작 위치 $N$개를 모두 검사하고도 같은 부분을 찾지 못하면 실패 알림을 띄우고 검사를 끝낸다.

로봇이 숫자 두 개를 한 번 비교할 때마다 상근이는 선영이에게 1원을 내야 한다.

금지된 시리얼 번호를 하나씩 검사할 때 상근이가 내야 하는 돈을 구하시오.

첫째 줄에 음식에 들어가는 시리얼 번호를 모두 이어 붙인 문자열의 길이 $N$이 주어지고, 둘째 줄에 그 문자열이 주어진다. ($1 \le N \le 100000$)

셋째 줄에 금지된 재료의 수 $M$이 주어진다. ($1 \le M \le 50000$) 다음 $M$개 줄에 금지된 시리얼 번호가 한 줄에 하나씩 주어진다.

모든 시리얼 번호는 0부터 9까지의 숫자로만 이루어진다. 금지된 시리얼 번호 하나의 길이는 $100000$을 넘지 않고, 금지된 시리얼 번호 길이의 총합은 $3000000$을 넘지 않는다.

금지된 시리얼 번호마다 로봇이 검사하는 데 드는 금액을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.