부분 집합 등식

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

📃 해결할 문제

에이전트들이 새로운 비밀 통신 방법을 시도하고 있습니다. 그들은 메시지 내용 중 중요한 정보를 숨기기 위해 불필요한 문자들을 섞어서 메시지를 해독하기 어렵게 만듭니다.

에이전트들은 두 개의 문자열 $s$ 와 $t$ 를 전송하며, 각 문자열의 길이는 최대 $10^5$ 입니다. 문자열은 영어 소문자 'a'부터 'r'까지만 포함하고 있습니다. 이 비밀 메시지를 해독하려고 $Q$ 개의 질의문이 주어집니다. 각 질의문은 'a'부터 'r'까지의 영어 소문자의 부분 집합을 제공합니다. 질문의 문자만을 포함하도록 $s$ 와 $t$ 가 제한될 때, 각 질의문에서 $s$ 와 $t$ 가 같은지 판별해야 합니다.

💻 입력

첫 번째 줄에는 문자열 $s$ 가 주어집니다.

두 번째 줄에는 문자열 $t$ 가 주어집니다.

세 번째 줄에는 $Q$ 가 주어집니다.

다음 $Q$ 줄 각각에는 질의문 문자열이 포함되어 있습니다. 질의문 문자열 안에서는 반복되는 문자가 없습니다. 또한, 모든 질의문 문자열은 정렬되어 있으며, 동일한 질의문 문자열은 한 번 이상 나타나지 않습니다.

🖨️ 출력

각 질의문에 대해, 질문의 문자에만 제한되어 있을 때

s

와

t

가 같다면 'Y'를, 그렇지 않다면 'N'을 출력합니다.

💻 예제 입력 1

aabcd
caabd
4
a
ac
abd
abcd

🖨️ 예제 출력 1

YNYN

💡 힌트

첫 번째 쿼리의 경우 'a'로만 제한되면 두 문자열 모두 "aa"가 됩니다.

두 번째 쿼리의 경우 첫 번째 문자열은 "aac"가 되고 두 번째 문자열은 "caa"가 됩니다.

점수:

테스트 케이스 2는 $|s|, |t|, Q \le 1000$ 을 만족합니다.
테스트 케이스 3-11은 추가적인 제약조건을 만족하지 않습니다.

출처: USACO 2022 US Open Contest, Silver Problem 2. Subset Equality