만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

신비한 장치

시간 제한2초메모리 제한1024 MB

요약
추가 버튼 n개와 삭제 버튼 m개로 빈 화면에서 시작해 각 질의 문자열 t를 만들 수 있는지 판단합니다.
난이도

보통10점 중 7점

유형
문자열 매칭, 트라이, 동적 계획법
정답자
아직 제출이 없습니다

문제

디마에게는 버튼이 n+mn + m개 있고 화면이 있는 장치가 있다. 화면에는 문자열 ss가 표시되며, 처음에는 빈 문자열이다.

ii번 버튼(1≤i≤n1 \le i \le n)을 누르면 문자열 wiw_i가 ss의 끝에 붙는다. n+in + i번 버튼(1≤i≤m1 \le i \le m)을 누르면 ss의 끝에서 aia_i개의 문자가 지워진다. ss의 길이가 aia_i보다 짧으면 ss는 빈 문자열이 된다.

디마에게는 좋아하는 문자열 tit_i가 qq개 있다. 각 문자열에 대해, 빈 문자열 ss에서 버튼을 여러 번 눌러 ss를 tit_i와 같게 만들 수 있는지 구한다.

입력

첫 줄에 첫 번째 종류와 두 번째 종류 버튼의 개수를 나타내는 정수 nn과 mm이 주어진다(1≤n,m≤1000001 \le n, m \le 100000).

다음 nn개의 줄에는 소문자 영문자로 이루어진 비어 있지 않은 문자열 wiw_i가 주어진다. 모든 wiw_i의 길이 합은 10610^6을 넘지 않는다.

다음 mm개의 줄에는 정수 aia_i(1≤ai≤1061 \le a_i \le 10^6)가 주어진다.

다음 줄에는 디마가 좋아하는 문자열의 개수를 나타내는 정수 qq(1≤q≤1000001 \le q \le 100000)가 주어진다.

다음 qq개의 줄에는 소문자 영문자로 이루어진 비어 있지 않은 문자열 tit_i가 주어진다. 모든 tit_i의 길이 합은 10610^6을 넘지 않는다.

출력

각 문자열 tit_i에 대해, ss를 tit_i와 같게 만들 수 있으면 Yes, 없으면 No를 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    2 1
    bba
    abacaba
    2
    4
    b
    ababbab
    abacabba
    caba
    
    예상 출력
    Yes
    Yes
    Yes
    No