Bạn đang tham gia trò chơi "đoán số hay, rinh lộc ngay" với cơ hội nhận về giải thưởng vô cùng hấp dẫn. Để trở thành người thắng cuộc, bạn cần vượt qua tất cả ~P~ vòng chơi. Ở mỗi vòng chơi, chương trình có một con số bí mật ~V~ và bạn cần tìm ra ẩn số này. Trước khi trò chơi bắt đầu, ban tổ chức thông báo một số nguyên ~D~ và cho bạn gợi ý: Ẩn số cần tìm ~V~ trong tất cả ~P~ vòng chơi đều là một số nguyên không nhỏ hơn ~1~ và không lớn hơn ~D~. Mỗi vòng chơi gồm một số lượt đoán số. Mỗi lượt đoán số diễn ra như sau: Bạn dự đoán một số nguyên ~H \in [1, 10^9]~. Ngay sau đó, ban tổ chức sẽ cho bạn biết các thông tin sau:

• Số ~H~ bạn đưa ra có trùng khớp với ẩn số ~V~ của chương trình hay không.
• Nếu không trùng khớp, bạn sẽ nhận được thông báo một giá trị ~X~ được xác định theo quy tắc sau:
  • Đặt ~X = \max(0, 1 - \frac{|V - H|}{V})~
  • Làm tròn giá trị ~X~ tới chính xác ba chữ số ở phần thập phân.

Bạn được coi là chiến thắng một vòng chơi nếu tìm ra ẩn số của chương trình sau không quá ~69~ lượt đoán số. Vượt qua cả ~P~ vòng chơi, bạn sẽ nhận được giải thưởng từ chương trình. Số lượt dự đoán số càng ít, giải thưởng của bạn càng lớn.

Tương tác

Đầu tiên, chương trình của bạn đọc hai số nguyên ~P~ và ~D~ (~1 \le P \le 1000; 1 \le D \le 10^9~) lần lượt là số vòng chơi và giới hạn ~D~ được thông báo trước khi trò chơi bắt đầu.

Tiếp theo, mỗi lượt đoán số diễn ra như sau:

• Trước tiên, bạn in ra số nguyên ~H~ (~1 \le H \le 10^9~) là con số bạn dự đoán.
• Sau đó, bạn đọc vào một số nguyên ~R~ (~R \in \{-1, 0, 1\}~) thể hiện phản hồi từ chương trình, cụ thể như sau:
  • ~R = 1~: giá trị ~H~ trùng khớp với ẩn số ~V~ cần tìm và bạn đã chiến thắng vòng chơi. Khi đó, chương trình của bạn cần chuyển sang vòng chơi tiếp theo, hoặc kết thúc ngay nếu đây là vòng chơi cuối cùng.
  • ~R = -1~: giá trị ~H~ bạn đưa ra không hợp lệ, hoặc bạn đã đoán vượt quá số lần cho phép. Khi đó, chương trình của bạn cần kết thúc ngay.
  • ~R = 0~: giá trị ~H~ chưa trùng khớp với ẩn số cần tìm. Khi đó, bạn đọc vào một số thực ~X~ được tính theo quy tắc ở trên.

Lưu ý: Sau khi bạn in ra một số nguyên, bạn cần in ra ký tự xuống dòng và thực hiện thao tác flush luồng ra chuẩn bằng cách gọi các lệnh sau:

• fflush(stdout) hoặc cout.flush() trong C++;
• System.out.flush() trong Java;
• stdout.flush() trong Python;

Chấm điểm

Nếu bạn không chiến thắng toàn bộ ~P~ vòng chơi, bạn được ~0~ điểm. Ngược lại, gọi ~Q~ là số lượt đoán số nhiều nhất bạn cần sử dụng trong một vòng chơi, số điểm của bạn được tính như sau:

• Nếu ~Q \le 25~, bạn được ~100\%~ số điểm của test.
• Nếu ~25 < Q \le 36~, bạn được ~((36 - Q)^2 \cdot 0.3 + (36 - Q) \cdot 1.7 + 45)\%~ số điểm của test.
• Nếu ~36 < Q \le 69~, bạn được ~((96 - Q)^2 \cdot 0.01 + 9)\%~ số điểm của test.

Scoring

• Subtask ~1~ (~4\%~ số điểm): ~D = 20~.
• Subtask ~2~ (~8\%~ số điểm): ~D = 100~.
• Subtask ~3~ (~8\%~ số điểm): ~D = 1000~.
• Subtask ~4~ (~16\%~ số điểm): ~D = 10^6~.
• Subtask ~5~ (~28\%~ số điểm): ~D = 5 \cdot 10^8~.
• Subtask ~6~ (~36\%~ số điểm): ~D = 10^9~.

Example