Connect Four là một trò chơi chiến thuật nổi tiếng. Trò chơi diễn ra trên một bảng cờ kích thước \(6\) hàng \(\times\) \(7\) cột.

• Hai người chơi lần lượt thả các quân cờ của mình vào một trong các cột từ \(1\) đến \(7\).
• Quân cờ sẽ rơi xuống vị trí thấp nhất chưa bị chiếm đóng trong cột đó do trọng lực.
• Người chơi nào tạo được 4 quân liên tiếp (theo hàng ngang, hàng dọc, hoặc đường chéo bất kỳ) trước sẽ giành chiến thắng.
• Nếu bảng cờ đầy mà không có ai thắng, trận đấu kết thúc với kết quả hòa.

Trong bài toán này, chương trình của bạn sẽ đóng vai trò là một Bot điều khiển quân Vàng (Player 2, đi sau) thi đấu trực tiếp theo dạng tương tác (Interactive) với Interactor (Trọng tài tự động của hệ thống) điều khiển quân Đỏ (Player 1, đi trước).

Input

• Dữ liệu tương tác được đọc trực tiếp từ luồng chuẩn trong quá trình chạy chương trình.
• Không có file input tĩnh nào được đọc trước.

Output

• Ở mỗi lượt đi của bạn, in ra một số nguyên duy nhất từ \(1\) đến \(7\) ứng với cột bạn chọn thả quân (Lưu ý phải flush đáp án).

Example

4
3
2

4
4
4