Đây là 1 bài Interactive

Trong bài toán này, bạn sẽ tham gia một trận đấu cờ vua trực tiếp với một con Bot siêu việt của hệ thống! Trên một bàn cờ tiêu chuẩn \(8 \times 8\), bạn sẽ cầm quân Trắng/Đen (\(\text{White}\)/\(\text{Black}\)) và đối đầu với Bot cầm quân Đen/Trắng (\(\text{Black}\)/\(\text{White}\)).(Lưu ý tỉ lệ để cầm các quân là 50%)

Nhiệm vụ của bạn là lập trình một thuật toán thông minh để gửi các nước đi hợp lệ theo định dạng chuẩn, đấu trí với Bot cho đến khi ván đấu kết thúc (chiếu hết, hòa, hoặc đạt số nước đi tối đa).

Đây là dạng bài toán interactive. Chương trình của bạn sẽ giao tiếp với chương trình chấm (interactor) thông qua luồng chuẩn (std::cin và std::cout).

1. Khởi đầu: Ván đấu bắt đầu, interactor sẽ in ra chuỗi khởi tạo startpos. Bạn cầm quân Trắng và là người đi trước.
2. Lượt đi của Bot: Sau mỗi nước đi của bạn, nếu ván đấu chưa kết thúc, interactor sẽ in ra nước đi của Bot theo định dạng UCI (ví dụ: e7e5).
3. Lượt đi của bạn: Chương trình của bạn đọc nước đi của Bot, tính toán, sauನೇ in ra nước đi của mình.

⚠️ Lưu ý quan trọng: Sau mỗi lần in ra một nước đi, bạn bắt buộc phải flush bộ đệm (cout << flush trong C++ hoặc sys.stdout.flush() trong Python), nếu không hệ thống sẽ báo lỗi Time Limit Exceeded hoặc Idleness Limit Exceeded.

Input

• Ban đầu và sau mỗi lượt đi của bạn, chương trình đọc vào một dòng duy nhất chứa chuỗi biểu diễn nước đi của đối thủ, hoặc trạng thái ván đấu.
• Nếu trận đấu kết thúc từ phía interactor, chuỗi nhận được có thể là 1-0, 0-1, hoặc 1/2-1/2. Khi nhận được kết quả này, chương trình của bạn phải kết thúc ngay lập tức (exit(0)).
• Nếu hoà cờ thì sẽ nhận được 0.5 số điểm.

Constraints

• Time limit: 3.0 giây cho toàn bộ ván đấu.
• Memory limit: 256 MB.
• Định dạng nước đi: Sử dụng chuẩn UCI (Universal Chess Interface), ví dụ: e2e4, g1f3, hoặc e7e8q nếu có phong hậu.
• Ngoài ra bài toán sẽ tuân theo mọi tiêu chuẩn của 1 bàn cờ thông thường(bao gồm cả nhập thành và bắt tốt qua đường).

Output

• Ở mỗi lượt của bạn, in ra một dòng duy nhất chứa nước đi của bạn theo định dạng UCI, kèm theo thao tác flush bộ đệm.

Example

startpos
e7e5
d7d5

e2e4
g1f3
e4d5

Bot

• Test 1-2: Elo 150-300 (Easy)
• Test 3-6: Elo 300-1000 (Medium)
• Test 7-10: Elo 1000-2000 (Hard)