Bạn có biết phòng thí nghiệm Just Odd Investigations không? Công việc của phòng thí nghiệm này là thực hiện những "nghiên cứu kỳ lạ" (just odd investigations). Sau đây, ta gọi tắt nơi này là phòng thí nghiệm JOI.

Trong những năm gần đây, người ta đã phát hiện những vườn hoa rộng lớn, nở rực rỡ tại nhiều di tích lịch sử trên thế giới. Phòng thí nghiệm JOI phát hiện rằng những bông hoa trong các khu vườn này thuộc các loài mới và bộ gen của chúng có những đặc điểm tương tự nhau. Bộ gen của mỗi bông hoa được biểu diễn bằng một xâu độ dài \(N\), chỉ gồm các ký tự J, O, I. Ta gọi xâu này là xâu gen.

Bạn là một nhà nghiên cứu tại phòng thí nghiệm JOI. Ban đầu, bạn có ba bông hoa thuộc các loài mới, với các xâu gen lần lượt là \(S_A\), \(S_B\), \(S_C\).

Bạn có thể tạo ra một bông hoa mới từ hai bông hoa bằng một thao tác gọi là lai giống. Ký tự thứ \(i\) (\(1 \le i \le N\)) trong xâu gen của bông hoa mới được xác định như sau:

• Nếu ký tự thứ \(i\) trong hai xâu gen ban đầu giống nhau, ký tự thứ \(i\) của xâu gen mới cũng là ký tự đó.
• Nếu hai ký tự này khác nhau, ký tự thứ \(i\) của xâu gen mới là ký tự còn lại trong ba ký tự J, O, I.

Nói cách khác, nếu ký tự thứ \(i\) của hai xâu gen ban đầu là \(c_1\) và \(c_2\), ký tự \(c_3\) ở vị trí đó của xâu gen mới được cho bởi bảng sau:

Bạn có thể sử dụng cùng một bông hoa để lai giống bao nhiêu lần tùy ý. Những bông hoa mới tạo ra cũng có thể được sử dụng trong các lần lai giống tiếp theo.

Để tạo ra những bông hoa đẹp hơn, phòng thí nghiệm JOI đề xuất \(Q+1\) xâu gen ứng viên, được đánh số từ \(0\) đến \(Q\). Bạn được cung cấp một danh sách mô tả các xâu này, gồm xâu \(T_0\) và, với mỗi \(j\) (\(1 \le j \le Q\)), hai số nguyên \(L_j\), \(R_j\) cùng ký tự \(C_j\). Các xâu gen ứng viên được xác định như sau:

• Xâu gen ứng viên \(0\) là \(T_0\).
• Xâu gen ứng viên \(j\) (\(1 \le j \le Q\)) được tạo từ xâu gen ứng viên \(j-1\) bằng cách thay tất cả các ký tự từ vị trí \(L_j\) đến vị trí \(R_j\) bằng ký tự \(C_j\).

Cho \(N\), các xâu gen của ba bông hoa ban đầu và danh sách mô tả các xâu gen ứng viên, hãy xác định với từng xâu ứng viên liệu có thể tạo được một bông hoa có xâu gen đó từ ba bông hoa ban đầu bằng cách thực hiện không hoặc nhiều lần lai giống hay không.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

N
S_A
S_B
S_C
Q
T_0
L_1 R_1 C_1
...
L_Q R_Q C_Q

Dữ liệu ra

Ghi \(Q+1\) dòng ra đầu ra chuẩn. Ở dòng thứ \(j+1\) (\(0 \le j \le Q\)), ghi Yes nếu có thể tạo được bông hoa có xâu gen ứng viên \(j\) từ ba bông hoa ban đầu bằng không hoặc nhiều lần lai giống; ngược lại, ghi No.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(S_A\), \(S_B\), \(S_C\) đều là các xâu độ dài \(N\), chỉ gồm các ký tự J, O, I.
• \(1 \le Q \le 200\,000\).
• \(T_0\) là xâu độ dài \(N\), chỉ gồm các ký tự J, O, I.
• \(1 \le L_j \le R_j \le N\) (\(1 \le j \le Q\)).
• \(C_j\) là một trong các ký tự J, O, I (\(1 \le j \le Q\)).

Phân nhóm

1. (3 điểm) \(S_A=S_B=S_C\) và \(N \le 100\).
2. (23 điểm) \(S_A=S_B=S_C\).
3. (23 điểm) \(N \le 100\).
4. (51 điểm) Không có giới hạn bổ sung.

Ví dụ

4
JOJO
JJOI
OJOO
3
IJOJ
1 4 O
2 2 J
2 4 I

Yes
No
Yes
Yes

3
JOI
JOI
JOI
2
OJI
1 2 O
1 1 J

No
No
Yes

Nguồn

JOI Open Contest 2021, JCIOI. Bản dịch tiếng Việt từ đề chính thức; phát hành theo giấy phép CC BY-SA 4.0.