Gooli là một công ty khổng lồ sở hữu \(B\) tòa nhà ở vùng đồi. Năm năm trước, Gooli xây các cầu trượt một chiều để nhân viên đi giữa các tòa nhà, mở đầu truyền thống xây cầu trượt. Hiện có \(S\) cầu trượt.

Melek, Trưởng bộ phận Giao thông và là người mê giải bài, phải giữ cho hệ thống thú vị. Cô vô hiệu hóa một số cầu trượt sao cho chỉ còn các chu trình. Một chu trình là tập ít nhất hai tòa nhà \(b_1,\ldots,b_k\) sao cho có đúng một cầu bật từ \(b_i\) tới \(b_{i+1}\) và đúng một cầu bật từ \(b_k\) về \(b_1\). Không cầu nào khác đi vào hay đi ra các tòa nhà đó được bật. Một trạng thái là vui nếu mỗi tòa nhà thuộc đúng một chu trình.

Cầu trượt được đánh số \(1\) đến \(S\). Bảng điều khiển có hai thao tác bật/tắt, mỗi thao tác nhận \(\ell,r,m\) và tác động mọi cầu \(x\) thỏa \(\ell\le x\le r\) và \(m\mid x\). Bật chỉ hợp lệ khi mọi cầu bị tác động đang tắt; tắt chỉ hợp lệ khi mọi cầu bị tác động đang bật.

Hình sau minh họa chuỗi trạng thái với \(3\) tòa nhà, \(3\) cầu; màu xám nhạt là tắt, xám đậm là bật:

1. Ban đầu, mọi cầu tắt.
   
2. Sau E 1 2 1, cầu \(1,2\) bật.
   
3. Sau E 3 3 1, cả \(1,2,3\) bật.
   
4. Sau D 1 3 2, cầu \(1,3\) bật.
   
5. Sau D 1 3 3, chỉ cầu \(1\) bật.
   
6. Sau E 1 2 2, cầu \(1,2\) bật.
   Trạng thái trở lại đúng như hình ở bước 2.

Sult, mèo của Melek, tìm thấy bảng và thực hiện nhiều thao tác hợp lệ. Sau mỗi thao tác, Melek muốn biết trạng thái có thể trở thành vui bằng cách bật đúng một cầu đang tắt hay không; cô không thật sự bật cầu đó.

Trong hình, sau thao tác thứ nhất, ba và cuối, bật cầu tắt duy nhất tạo trạng thái vui. Sau thao tác thứ hai, không còn cầu tắt; hơn nữa trạng thái đã vui nên bật thêm bất kỳ cầu nào cũng phá tính vui. Sau thao tác thứ tư, có hai cầu tắt nhưng bật cầu nào cũng không vui.

Ban đầu mọi cầu tắt. Sau mỗi thao tác của Sult, hãy xác định cầu tắt nào, nếu có, Melek có thể bật để trạng thái vui.

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ bắt đầu bằng \(B,S,N\). Tiếp theo \(S\) dòng; dòng \(i\) chứa \(X_i,Y_i\), nghĩa là cầu \(i\) đi từ \(X_i\) tới \(Y_i\). Cuối cùng \(N\) dòng chứa \(A_j,L_j,R_j,M_j\); \(A_j\) là E hoặc D, tác động các số cầu vừa thuộc \([L_j,R_j]\) vừa chia hết cho \(M_j\).

Dữ liệu ra

Với mỗi bộ, in Case #x: y_1 ... y_N. \(y_j\) là X nếu không thể bật đúng một cầu tắt để trạng thái sau \(j\) thao tác trở thành vui; nếu có, \(y_j\) là số hiệu một cầu như vậy.

Ràng buộc

• \(1\le X_i,Y_i\le B\), \(X_i\ne Y_i\); mọi cặp \((X_i,Y_i)\) phân biệt.
• \(A_j\in\{\mathtt E,\mathtt D\}\); \(1\le L_j\le R_j\le S\); \(1\le M_j\le S\).
• Mọi thao tác đều hợp lệ.

Phân nhóm

• Test Set 1 (Visible Verdict): \(1\le T\le100\); \(2\le B\le100\); \(2\le S\le1000\); \(1\le N\le1000\).
• Test Set 2 (Hidden Verdict): \(1\le T\le30\); \(2\le B\le3\cdot10^4\); \(2\le S\le3\cdot10^5\); \(1\le N\le3\cdot10^5\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
3 3 5
1 2
2 3
3 1
E 1 2 1
E 3 3 1
D 1 3 2
D 1 3 3
E 1 2 2
5 8 10
1 5
5 3
4 1
3 2
2 4
2 5
2 1
1 4
E 1 8 2
D 4 8 2
E 3 5 1
E 1 1 3
E 1 1 1
E 5 8 2
D 1 8 3
D 5 8 4
D 4 5 1
E 3 4 1

Case #1: 3 X 2 X 3
Case #2: 3 X 1 1 X X X 3 X 5

Nguồn

Google Code Jam 2021, Chung kết thế giới, bài Slide Circuits.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.