Bạn có một tòa nhà gồm n tầng (đánh số từ 1 đến n) và chính xác 2 quả trứng giống hệt nhau. Tồn tại một tầng tới hạn f sao cho:

• Nếu thả một quả trứng từ tầng f hoặc thấp hơn, nó sẽ không vỡ
• Nếu thả một quả trứng từ bất kỳ tầng nào cao hơn f, nó sẽ vỡ

Nhiệm vụ của bạn là xác định tầng tới hạn f bằng cách thả trứng từ các tầng khác nhau. Khi một quả trứng bị vỡ, bạn không thể sử dụng nó được nữa. Nếu quả trứng không vỡ, bạn có thể dùng lại nó cho các lần thử tiếp theo.

Mục tiêu của bạn là tìm ra tầng tới hạn với số lần thả ít nhất có thể, kể cả trong trường hợp xấu nhất.

Đầu vào/Đầu ra (Tương tác)

Đây là một bài toán tương tác. Chương trình của bạn phải tương tác với hệ thống chấm bằng cách luân phiên đọc đầu vào và ghi đầu ra.

Đầu vào ban đầu

Dòng đầu tiên chứa một số nguyên duy nhất n (1 ≤ n ≤ 10⁹) - số tầng của tòa nhà.

Giao thức tương tác

Sau khi đọc n, chương trình của bạn phải liên tục đưa ra các truy vấn thả trứng cho đến khi xác định được tầng tới hạn:

1. Xuất một truy vấn: In ra một số nguyên duy nhất k (1 ≤ k ≤ n) - số thứ tự tầng mà bạn muốn thả trứng
2. Xả bộ đệm đầu ra: Sử dụng System.out.flush() trong Java
3. Đọc phản hồi: Đọc một chuỗi từ đầu vào, chuỗi này sẽ là một trong các trường hợp sau:
   • "SAFE" - Quả trứng không vỡ (tầng tới hạn nằm ở tầng k hoặc cao hơn)
   • "BROKEN" - Quả trứng bị vỡ (tầng tới hạn nằm dưới tầng k)

Sau khi đã xác định được tầng tới hạn, hãy xuất câu trả lời của bạn:

1. Xuất câu trả lời: In ra ! f trong đó f là tầng tới hạn (1 ≤ f ≤ n)

Lưu ý quan trọng: Bạn phải xả bộ đệm đầu ra sau mỗi truy vấn, nếu không hệ thống chấm sẽ không nhận được đầu ra và chương trình sẽ bị treo.

Ràng buộc nghiêm ngặt: Bạn chỉ có 2 quả trứng. Nếu cả 2 quả trứng đều vỡ trước khi bạn tìm ra câu trả lời, bạn sẽ nhận được kết quả "Wrong Answer".

Cách tính điểm

• Mỗi bộ test được tính điểm dựa trên số lần thả tối đa mà bạn thực hiện trong trường hợp xấu nhất. Các lời giải sử dụng ít lần thả hơn sẽ nhận được điểm cao hơn. Tổng điểm là tổng điểm của tất cả các bộ test.

Ví dụ về quá trình tương tác

Judge: 10
You:   4
Judge: SAFE
You:   7
Judge: BROKEN
You:   5
Judge: SAFE
You:   6
Judge: BROKEN
You:   ! 5

Trong ví dụ này:

• Tòa nhà có 10 tầng
• Thả từ tầng 4 → SAFE (f ≥ 4)
• Thả từ tầng 7 → BROKEN (f < 7, quả trứng thứ nhất bị vỡ)
• Thả từ tầng 5 → SAFE (f ≥ 5, sử dụng quả trứng thứ hai)
• Thả từ tầng 6 → BROKEN (f < 6, quả trứng thứ hai bị vỡ)
• Kết luận: f = 5

Lời giải đã thực hiện 4 lần thả để tìm ra tầng tới hạn.

Các ràng buộc

• 1 ≤ n ≤ 10⁹
• Bạn có chính xác 2 quả trứng
• Bạn có thể thực hiện tối đa 2000 lần thả cho mỗi bộ test
• Tầng tới hạn f là cố định đối với mỗi bộ test (1 ≤ f ≤ n)