Xét trò chơi niềm tin giữa hai người chơi sau đây. Lưu ý rằng trò chơi này có thể khác với một trò chơi mà bạn từng biết.

• Khi một người chơi bỏ một đồng xu vào máy, người chơi kia nhận được ba đồng xu.
• Trò chơi kéo dài \(2m\) lượt. Hai người luân phiên hành động; ở mỗi lượt, người đang hành động chọn một trong hai cách:
• Hợp tác: bỏ vào một đồng xu.
• Lừa dối: không bỏ đồng xu.
• Nếu hợp tác, người hành động mất một đồng xu và người kia nhận ba đồng xu. Nếu lừa dối, không có gì xảy ra.
• Sau mỗi lượt, người chơi kia biết lựa chọn vừa được thực hiện.

Bạn chơi với một máy lặp lại và đi trước. Chiến lược của máy được mô tả bởi một đa tập \(S\) gồm các xâu nhị phân có độ dài không quá \(m\). Máy chọn ngẫu nhiên đều một xâu \(s\in S\). Gọi \(k=|s|\). Ở lượt \(2i\) (\(1\le i\le m\)), tức hành động thứ \(i\) của máy:

• Nếu \(1\le i\le k\), máy hợp tác khi \(s_i=0\) và lừa dối khi \(s_i=1\).
• Nếu \(k<i\le m\), máy lặp lại lựa chọn gần nhất của bạn, tức lựa chọn ở lượt \(2i-1\).

Ban đầu tập chiến lược chưa được xác định. Có \(n\) thao tác; thao tác thứ \(i\) cho xâu nhị phân \(s_i\) và số nguyên \(a_i\):

• Nếu \(a_i>0\), thêm \(a_i\) bản sao của \(s_i\) vào \(S\).
• Nếu \(a_i<0\), xóa \(-a_i\) bản sao của \(s_i\) khỏi \(S\). Đề bảo đảm trước khi xóa có đủ số bản sao và sau khi xóa, \(S\) vẫn chứa ít nhất một xâu.

Sau mỗi thao tác, hãy tính kỳ vọng lớn nhất của số xu bạn thu được khi chơi tối ưu. Các truy vấn sau từng thao tác độc lập với nhau. Bạn biết toàn bộ đa tập \(S\) nhưng không biết máy đã chọn xâu cụ thể nào; mỗi hành động của bạn có thể phụ thuộc vào tất cả lựa chọn trước đó của cả hai bên.

Bạn chỉ cần in kỳ vọng nhân với \(|S|\). Có thể chứng minh kết quả này là một số nguyên.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương \(n,m\).
• Dòng thứ \(i+1\) chứa một xâu nhị phân \(s_i\) có độ dài không quá \(m\) và một số nguyên \(a_i\).

Dữ liệu ra

In \(n\) dòng. Dòng thứ \(i\) là đáp án sau thao tác thứ \(i\).

Ràng buộc

Nếu \(a_i<0\), trước thao tác có ít nhất \(-a_i\) bản sao của \(s_i\) trong \(S\) và sau thao tác \(S\) vẫn chứa ít nhất một xâu.

Chấm điểm

• Tính chất A: \(a_i=1\) với mọi \(i\) và \(\sum_{i=1}^{n}|s_i|\le5000\).
• Tính chất B: \(|s_i|\ge|s_{i+1}|\) với mọi \(1\le i<n\).

Trong từng phần:

• Chỉ trả lời đúng đáp án sau thao tác thứ \(n\) trên mọi tệp nhận được \(40\%\) số điểm của phần.
• Trả lời đúng đáp án sau mọi thao tác nhận được \(100\%\) số điểm của phần.

Ngay cả khi chỉ trả lời thao tác cuối, bạn vẫn phải in đủ \(n\) số nguyên, tương ứng với đáp án sau từng thao tác.

Ví dụ

8 3
111 1
1 1
0 1
011 4
1 -1
01 3
011 -3
0 3

0
3
10
18
15
28
22
41

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.