Bạn có \(N\) viên gạch được đánh số từ \(1\) đến \(N\). Mặt trên và mặt dưới của mỗi viên có màu đen (B) hoặc trắng (W); ký tự thứ \(i\) của chuỗi \(S\) và \(T\) lần lượt cho biết màu mặt trên và mặt dưới ban đầu của viên \(i\).

Uzbekistan nổi tiếng với những công trình kiến trúc lịch sử được trang trí bằng gạch. Khi tham quan các thánh đường Hồi giáo và trường học Hồi giáo (madrasa) ở Uzbekistan, bạn bị cuốn hút bởi vẻ đẹp của những công trình này và mua một cỗ máy kỳ lạ liên quan đến gạch. Cỗ máy có hai khay ở bên trái và bên phải, mỗi khay đặt được một viên gạch. Khi đặt viên gạch \(a\) ở khay trái và viên gạch \(b\) ở khay phải, máy đổi hai viên này lấy một viên mới \(c\) theo các quy tắc sau:

• Mặt trên của \(c\) màu đen khi và chỉ khi màu mặt dưới của \(a\) bằng màu mặt trên của \(b\); nếu không thì màu trắng.
• Mặt dưới của \(c\) màu đen khi và chỉ khi màu mặt trên của \(a\) bằng màu mặt dưới của \(b\); nếu không thì màu trắng.

Trong \(Q\) ngày, ngày \(j\) thực hiện một trong hai hành động:

• Loại 1: đổi màu mặt trên và mặt dưới của viên \(X_j\) lần lượt thành \(Y_j\) và \(Z_j\).
• Loại 2: xếp các viên \(L_j,L_j+1,\ldots,R_j\) theo thứ tự từ trái sang phải. Có thể thực hiện từ \(0\) đến \(R_j-L_j\) lần thao tác sau: chọn hai viên kề nhau, bỏ chúng khỏi hàng, đưa viên bên trái vào khay trái và viên bên phải vào khay phải, rồi đặt viên mới do máy tạo ra vào đúng vị trí của cặp vừa bỏ. Hãy xác định có thể thực hiện các thao tác để trong hàng có đúng \(M_j\) viên có mặt trên màu trắng (các viên khác trong hàng vẫn có thể có mặt trên màu đen) hay không.

Mỗi truy vấn loại 2 chỉ là một thí nghiệm độc lập và không làm thay đổi các viên gạch; chỉ cập nhật loại 1 mới thay đổi trạng thái dùng cho các ngày sau.

Dữ liệu vào

Dữ liệu vào có dạng:

N
S
T
Q
(Query 1)
...
(Query Q)

Gọi \(P_j\) là số nguyên đầu tiên của truy vấn thứ \(j\). Mỗi truy vấn là một trong hai dạng:

• 1 X_j Y_j Z_j: cập nhật viên \(X_j\).
• 2 L_j R_j M_j: thực hiện thí nghiệm trên đoạn \([L_j,R_j]\).

Dữ liệu ra

Với mỗi truy vấn loại 2, theo thứ tự xuất hiện, in Yes nếu có thể tạo đúng số viên mặt trên trắng được yêu cầu, ngược lại in No.

Ràng buộc

• \(1\le N\le300\,000\).
• \(S,T\) là các chuỗi độ dài \(N\) chỉ gồm B và W.
• \(1\le Q\le300\,000\).
• \(P_j\in\{1,2\}\) với mọi \(1\le j\le Q\).
• Nếu \(P_j=1\): \(1\le X_j\le N\) và \(Y_j,Z_j\in\{\texttt{B},\texttt{W}\}\).
• Nếu \(P_j=2\): \(1\le L_j\le R_j\le N\) và \(0\le M_j\le R_j-L_j+1\).
• Mọi giá trị số trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(6\) điểm: \(N\le6\).
2. \(10\) điểm: \(N\le100\) và mọi truy vấn có loại \(2\).
3. \(9\) điểm: \(N\le500\) và mọi truy vấn có loại \(2\).
4. \(8\) điểm: \(N\le1700\) và mọi truy vấn có loại \(2\).
5. \(23\) điểm: \(N,Q\le10000\).
6. \(14\) điểm: \(N,Q\le100000\).
7. \(30\) điểm: không có ràng buộc thêm.

Ví dụ

4
WBWB
BWBB
5
2 3 4 1
2 1 2 0
1 3 B B
2 3 4 2
2 2 4 1

Yes
Yes
No
Yes

6
BWBWWB
WBWBBB
8
2 1 3 2
2 2 6 0
2 1 5 3
2 3 3 0
2 3 4 1
2 5 6 2
2 2 6 4
2 1 4 2

No
Yes
Yes
Yes
Yes
No
No
Yes

Nguồn

JOI 2025/2026 Semifinal Stage, bài Strange Machine. Tài liệu gốc của Japanese Committee for IOI được phát hành theo CC BY-SA 4.0.