Cho một đa giác lồi gồm ~n~ đỉnh trên hệ trục tọa độ ~OXY~. Các điểm được đánh số từ ~p_1,p_2,...,p_n~.

Với mỗi điểm ~p_i~ ~(1 \le i \le n)~, hãy xác định chu vi lớn nhất của lục giác gồm các điểm trên đa giác và chứa điểm ~i~.

Input

• Dòng đầu gồm số nguyên dương ~n~.
• ~n~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên dương ~x_i,y_i~ miêu tả tọa độ của điểm thứ ~i~. Các điểm được cho theo chiều ngược kim đồng hồ.

Output

• Gồm ~n~ dòng, dòng thứ ~i~ in ra chu vi lớn nhất của lục giác gồm các điểm trên đa giác và chứa điểm ~i~. Kết quả làm tròn đến số thứ ~4~ sau dấu phẩy.

Constraints .

• ~1 \le n \le 1000~.
• ~|x_i|,|y_i| \le 10^9~.

Subtask

• Sub ~1~ (~30\%~): ~n \le 10~.
• Sub ~2~ (~30\%~): ~n \le 100~.
• Sub ~3~ (~40\%~): ~n \le 1000~.

Sample Input 1

8
0 3
1 1
3 0 
6 2
5 5
3 6
1 5
5 0

Sample Output 1

27.3183
26.8052
27.3183
27.3183
27.2445
27.3183
27.3183
27.3183

Trong những ghi chép cổ xưa có những thông tin về một pháo đài cổ ở thành Vinh trên bản đồ phẳng với hệ tọa độ Descartes vuông góc Oxy. Nền pháo đài có dạng hình chữ nhật với các cạnh song song với một trong hai trục tọa độ. Những khảo sát gần đây tại vị trí ~(x_0, y_0)~ đã khẳng định chắc chắn vị trí ~(x_0,y_0)~ nằm trong pháo đài cổ xưa.

Em được yêu cầu xác định vị trí ban đầu acủa nền pháo đài cổ bằng một robot hoạt động theo quy trình sau. Tại mỗi bước, em yêu cầu robot đào sâu xuống khảo sát tại một vị trí do em lựa chọn. Robot sẽ báo cáo có tìm thấy dấu vết của pháo đài cổ tại vị trí đó hay không? Vì chi phí của mỗi lần khảo sát khá lớn nên em cần yêu cầu robot khảo sát tại càng ít vị trí càng tốt.

Nhiệm vụ của em là viết một chương trình có tên CITADEL.*, sử dụng các lệnh được cung cấp để thực hiện khảo sát các vị trí, nhận kết quả khảo sát và đưa ra đánh giá về vị trí chính xác của khu pháo đài cổ.

Input

• Hai số ~x_0, y_0~ được cho đầu chương trình.

Interaction

Để tương tác với máy chấm, em hãy in mỗi lệnh trên từng dòng. Câu trả lời sẽ được máy chấm in ra trên một dòng khác, và em đọc vào. Lưu ý, nhớ flush luồng ra chuẩn sau mỗi dòng được in ra bằng lệnh fflush(stdout) hoặc cout << endl;

Các lệnh được sử dụng:

• find x y

  Em chỉ được phép dùng lệnh này tối đa một triệu lần. Máy chấm in ra ~0~ hoặc ~1~:

  • 0 tương ứng với không tìm thấy dấu vết tại vị trí có tọa độ ~(x,y)~. Nói cách khác là vị trí ~(x,y)~ nằm phía ngoài nền pháo đài cổ.
  • 1 tương ứng với có tìm thấy dấu vết tại vị trí có tọa độ ~(x,y)~. Nói cách khác là vị trí ~(x,y)~ nằm ở phía trong hoặc trên biên nền của pháo đài cổ.
  • Nếu lệnh này được dùng quá một triệu lần, chương trình sẽ bị ngắt và ghi nhận ~0~ điểm với test em đang chạy.

• answer x1 y1 x2 y2

  Lệnh này chỉ được in ra đúng 1 lần trước khi kết thúc chương trình để cho biết về kết quả mà em xác định được; trong đó ~(x_1, y_1)~ là tọa độ góc trái dưới của nền pháo đài, ~(x_2, y_2)~ là tọa độ góc phải trên của nền pháo đài.

Chương trình bắt buộc phải in lệnh answer một lần duy nhất, nếu không sẽ bị 0 điểm. Sau khi em in ra lệnh này, chương trình sẽ được ngắt.

Scoring

Bài thi của em được chấm trên ~20~ test, mỗi test tối đa ~5~ điểm.

• Trong các test ~1,2,3,..,6~: tọa độ của pháo đài có giá trị tuyệt đối không vượt quá ~200~
• Trong các test ~7,8,9,...,13~: tọa độ của pháo đài có giá trị tuyệt đối không vượt quá ~2 \times 10^5~
• Trong các test còn lại ~14,14,15,...,20~: tọa độ của pháo đài có giá trị tuyệt đối không vượt quá ~2 \times 10^9~

Với mỗi test, nếu chương trình của em in ra lệnh answer với các tham số không chính xác, chạy quá thời gian quy định hoặc gặp các lỗi dẫn tới dừng chương trình, bài làm sẽ nhận ~0~ điểm cho test đó. Ngược lại, bài làm sẽ nhận được số điểm trong khoảng từ ~1~ đến ~5~ cho test đó phụ thuộc vào số lần sử dụng lệnh find nhiều hay ít.

Example

Sample Input

3 1
1
0
0
1
1
1
0
0
0

Sample Output

find 3 -1
find 3 -2
find -4 -1
find -1 1
find -3 1
find 8 2
find 9 3
find 9 1
find 7 3
answer -3 -1 8 2

Note

Bạn cần đoán một xâu bí mật ~s~ độ dài ~n~ chỉ gồm các ký tự ~\{a, b, c\}~.

Để làm vậy, bạn có thể thực hiện truy vấn sau:

• ~?~ ~t~ — bạn chọn một xâu ~t~ bất kỳ và hệ thống trả về độ dài xâu con chung dài nhất (LCS) của ~s~ và ~t~.

Khi bạn đã biết chính xác xâu ~s~, hãy in ra kết quả.

Lưu ý: Số lượng truy vấn không được vượt quá ~\left\lfloor \frac{5}{3} n \right\rfloor + 1~.

Input

Output

Interaction

Ban đầu, bạn cần đọc vào số nguyên ~n~ ~(1 \le n \le 1000)~ — độ dài của xâu bí mật ~s~.

Để thực hiện truy vấn, in ra "? t" và đọc vào một số nguyên — độ dài LCS của ~s~ và ~t~. Xâu ~t~ phải là xâu không rỗng chỉ gồm các ký tự ~\{a, b, c\}~.

Khi đã biết kết quả, in ra "! s" — xâu bí mật ~s~. Chương trình của bạn phải kết thúc sau khi in ra kết quả này.

Nếu bạn nhận được kết quả là ~-1~ khi thực hiện truy vấn thì bạn đã thực hiện nhiều lượt truy vấn hơn cho phép hoặc thực hiện một truy vấn không hợp lệ. Chương trình của bạn phải kết thúc ngay và sẽ nhận được kết quả Wrong Answer.

Scoring

• ~1 \le n \le 1000~

• Xâu ~s~ chỉ gồm các ký tự ~\{a, b, c\}~

• Số lượng truy vấn không vượt quá ~\left\lfloor \frac{5}{3} n \right\rfloor + 1~

Sample Input 1

4
2
1
2
4

Sample Output 1

? aaaa
? bbbb
? ab
? abac
! abac

Notes

Xâu bí mật là ~s = \texttt{"abac"}~, ~n = 4~.

• Truy vấn "aaaa": ~LCS(\texttt{"abac"}, \texttt{"aaaa"}) = 2~.

• Truy vấn "bbbb": ~LCS(\texttt{"abac"}, \texttt{"bbbb"}) = 1~.

• Từ đó suy ra: ~cnt_a = 2,\; cnt_b = 1,\; cnt_c = 1~.

• Các truy vấn tiếp theo xây dựng xâu và đoán đúng ~s = \texttt{"abac"}~.

Anya và Bob chơi một trò chơi trên cây.

Có ~n~ đỉnh, đánh số từ ~0~ đến ~n-1~, và có đúng ~n-1~ cạnh. Đồ thị luôn liên thông, nên đây là một cây.

Trò chơi có 2 pha:

• Pha 1 (Anya): Anya biết toàn bộ cây, chọn thứ tự xóa ~l_0, l_1, \ldots, l_{n-2}~ sao cho ở mỗi bước, đỉnh bị xóa là lá trong cây còn lại. Đồng thời Anya gửi một thông điệp nhị phân message cho Bob.
• Pha 2 (Bob): Bob không biết cây ban đầu. Ở bước ~i~, Bob nhận một cặp ~(a,b)~ với ~a<b~, là một cạnh còn tồn tại ở thời điểm đó. Một trong hai đỉnh là lá đúng cần xóa (~l_i~), đỉnh còn lại là hàng xóm sống duy nhất của lá đó. Bob phải chọn đúng lá.</li>

Nếu Bob sai ở bất kỳ bước nào, lời giải thất bại.

Yêu cầu

Cài đặt chiến lược cho Anya và Bob để Bob luôn chọn đúng.

Nộp bài

Nộp 1 file C++:

#include "findleaf.h"

Các hàm cần cài đặt

Namespace Anya

void InitAnya(int N, const std::vector<int>& A, const std::vector<int>& B);

• Gọi đúng 1 lần.
• N là số đỉnh (tương ứng với ~n~).
• Cạnh thứ i nối A[i] và B[i].

std::string CreateMessage();

• Trả về chuỗi nhị phân chỉ gồm '0' và '1'.
• Độ dài chuỗi không quá 1000.

std::vector<int> CreateOrder();

• Trả về thứ tự xóa gồm đúng N-1 đỉnh.
• Mỗi đỉnh xuất hiện nhiều nhất 1 lần.
• Tại từng bước, đỉnh được xóa phải là lá hợp lệ trong cây hiện tại.

Namespace Bob

void InitBob(int N, const std::string& message);

• Gọi đúng 1 lần trước các bước của Bob.

int RemoveLeaf(int a, int b);

• Gọi đúng N-1 lần.
• Luôn có a < b.
• (a,b) là cạnh còn tồn tại ở bước hiện tại.
• Một trong hai đỉnh là lá đúng cần xóa.
• Trả về đỉnh Bob chọn (a hoặc b).

Cách grader local mô phỏng

1. Đọc cây đầu vào.
2. Gọi Anya::InitAnya(...).
3. Lấy message = Anya::CreateMessage() và order = Anya::CreateOrder().
4. Kiểm tra format message, độ dài và tính hợp lệ của order.
5. Gọi Bob::InitBob(N, message).
6. Mô phỏng từng bước xóa theo order, tạo cặp (a,b) tương ứng rồi gọi Bob::RemoveLeaf(a,b).
7. Nếu Bob sai ở bất kỳ bước nào thì fail.

Đầu ra của grader:

• In K = |message| nếu lời giải đúng.
• In -1 nếu sai.

Chấm điểm theo ~K~

Checker dùng các mức sau:

• 500 <= K <= 1000: 15%
• 50 <= K < 500: 20%
• 10 <= K < 50: 30%
• 0 <= K < 10: 20%
• K = -1 hoặc ngoài miền hợp lệ: WA

Ràng buộc

• ~1 \le n \le 1000~
• Input luôn là cây hợp lệ.

Cấu trúc bộ test

Tổng cộng 20 test:

• 4 test cây star.
• 4 test cây line.
• 4 test cây star with lines (mọi đỉnh bậc 1/2, trừ đúng 1 đỉnh có bậc >2).
• 8 test cây random.

Ví dụ

Đây là ví dụ ở pha 1 (Anya). Một input hợp lệ:

grader output
7
0 1
1 2
2 3
0 4
0 6
1 5

Một output hợp lệ tương ứng:

your output
0110
5
3
2
6
4
0

Trong đó:

• 0110 là thông điệp nhị phân Anya gửi.
• Dãy 5, 3, 2, 6, 4, 0 là thứ tự xóa lá.