USACO 2022 US Open Contest, Silver, Subset Equality

Xem PDF

Điểm: 1000 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Những con bò đang thử phương pháp mới để trao đổi các tin nhắn được mã hóa với nhau, trong đó chúng trộn các chữ cái không liên quan vào giữa tin nhắn để làm cho các tin nhắn khó giải mã.

Những con bò truyền nhau hai xâu \(s\)\(t\), mỗi xâu có độ dài tối đa \(10^5\) và chỉ bao gồm các chữ cái tiếng Anh viết thường từ a đến r. Để thử và hiểu thông điệp được mã hóa này, bạn sẽ nhận được truy vấn \(Q(1\leq Q\leq 10^5)\). Mỗi truy vấn cung cấp một tập hợp con các chữ cái tiếng Anh viết thường từ a đến r: Nếu chỉ giữ lại các chữ cái có trong tập con ở hai xâu \(s\)\(t\) thì hai xâu có bằng nhau hay không.

Input

  • Dòng đầu tiên chứa xâu \(s\).
  • Dòng thứ hai chứa xâu \(t\).
  • Dòng thứ ba chứa số \(Q\).
  • \(Q\) dòng tiếp theo, mỗi dòng chứa một xâu truy vấn. Trong xâu được cho, không có chữ cái nào được lặp lại. Hơn nữa, tất cả các xâu truy vấn đều được sắp xếp theo thứ tự và không có xâu truy vấn nào xuất hiện nhiều lần.

Output

Với mỗi truy vấn, in ra Y nếu các kí tự được giữ lại ở \(2\) xâu tạo thành \(2\) xâu bằng nhau; ngược lại, in ra N.

Scoring

  • Subtask \(1\): \(|s|,|t|,Q \leq 1000\).
  • Subtask \(2\): Không có điều kiện gì thêm.

Example

Test 1

Input
aabcd
caabd
4
a
ac
abd
abcd
Output
YNYN
Note
  • Với truy vấn đầu tiên, cả \(2\) xâu đều trở thành aa.
  • Với truy vấn thứ hai, xâu \(s\) trở thành aac, còn xâu \(t\) trở thành caa.

Bình luận

Không có bình luận nào.