Hôm nay, lớp của Cam có một trò chơi trong giờ Toán. Có n miếng gà: ~p[0], p[1], \ldots, p[n - 1]~. Trong số đó có một miếng ngon nhất bí mật là ~p[b]~.

Bạn được so sánh độ ngon giữa hai miếng gà thông qua hàm find_better(i, j), hàm sẽ trả về chỉ số của miếng gà ngon hơn.

Mục tiêu: Tìm ra chỉ số của miếng gà ngon nhất, đồng thời tối ưu số lần gọi hàm find_better() trên miếng gà ngon nhất.

Input

Output

Interaction

Đầu tiên, đọc số nguyên ~n~ ~(2 \leq n \leq 10^5)~ trên một dòng.

Để tương tác với trình chấm, in mỗi lệnh trên một dòng riêng, lưu ý phải flush output bằng fflush(stdout) hoặc cout.flush.

Các câu lệnh:

• ? i j: Trình chấm gọi find_better(i, j) và trả về chỉ số của miếng gà ngon hơn

• answer b: Trả lời chỉ số của miếng gà ngon nhất là ~p[b]~ mà bạn tìm được. Chương trình phải in answer chính xác một lần.

Scoring

Nếu chương trình đưa ra kết quả answer sai, hoặc dùng quá ~10^6~ lần hỏi, hoặc bị lỗi làm chương trình kết thúc bất thường thì test đó sẽ nhận ~0~ điểm.

Ngược lại, gọi ~T~ là điểm tối đa của test đó, ~L~ là đáp án của giám khảo, và ~X~ là số lần chương trình của thí sinh gọi hàm find_better() trên miếng ngon nhất. Số điểm thí sinh nhận được cho test này được tính theo công thức:

$$\text{Điểm} = \begin{cases} T & \text{nếu } X \le L \\ \frac{\max(0, 100 - (X - L) \cdot 6)}{100} \cdot T & \text{nếu } X > L \end{cases}$$

Notes

Giả sử miếng gà ngon nhất là ~p[2]~ và ~n = 4~:

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"}~.

Nhiều nơi ở Nga có tuyết phủ. Ở Nga có ~n~ thành phố, được đánh số từ ~0~ đến ~n-1~.

Nga có ~n-1~ con đường, được đánh số từ ~0~ đến ~n-2~. Đường số ~i~ (~0 \le i \le n-2~) nối hai thành phố khác nhau là ~A[i]~ và ~B[i]~ (~0 \le A[i] < B[i] \le n-1~) theo hai chiều. Giữa mọi cặp thành phố khác nhau, luôn có thể đi từ thành phố này sang thành phố kia bằng cách đi qua một số con đường.

Tình trạng tuyết trên mỗi con đường thay đổi theo từng ngày. Với mỗi ngày, mỗi con đường ở một trong hai trạng thái:

• Có tuyết rơi
• Không có tuyết rơi

Trong cùng một ngày, trạng thái không thay đổi.

Anya và Boris làm việc ở bưu điện viễn thông của Nga.

• Anya thuộc bộ phận quản lý thông tin đường sá.
• Boris thuộc bộ phận trả lời câu hỏi của người dân.

Câu hỏi của người dân là:

Để đi từ thủ đô (thành phố 0) đến một thành phố nào đó, cần đi qua ít nhất bao nhiêu con đường đang có tuyết?

Bình thường, sau khi nhận câu hỏi, Boris sẽ tương tác với Anya để trả lời.

Hiện tại, có một cuộc thi lập trình quốc tế kéo dài ~q~ ngày diễn ra ở Nga. Trong thời gian thi, đường truyền bận nên Anya và Boris khó tương tác trực tiếp. Vì vậy họ thống nhất tương tác qua máy chủ trung gian như sau:

• Đầu mỗi ngày, Anya tổng hợp thông tin tuyết của ngày đó và gửi dữ liệu lên máy chủ trung gian.
• Khi Boris nhận câu hỏi từ người dân, Boris sẽ tương tác với máy chủ trung gian để trả lời.

Tuy nhiên, việc tương tác bị giới hạn:

• Dung lượng máy chủ trung gian là ~l = 1000~ bit. Anya chỉ có thể lưu tối đa ~1000~ bit mỗi ngày.
• Dữ liệu trên máy chủ sẽ được reset về ~0~ vào đầu mỗi ngày.
• Mỗi lần hỏi máy chủ, Boris chỉ đọc được ~1~ bit ở vị trí chỉ định.
• Để trả lời mỗi câu hỏi, Boris được phép tương tác tối đa ~20~ lần.

Bạn là người quen của giám đốc, nên bạn sẽ hướng dẫn chiến lược cho Anya và Boris.

Hãy viết chương trình cài đặt chiến lược để Boris luôn trả lời đúng cho người dân.

Giao thức tương tác

Bạn phải nộp một file bao gồm các namespace Anya và Boris:

#include "snowcity.h"

Namespace Anya

Cài đặt chiến lược của Anya, và phải có 2 hàm:

void InitAnya(int N, vector<int> A, vector<int> B)

Hàm này sẽ được gọi đúng 1 lần cho mỗi test.

• N: số thành phố (~n~).
• A, B: vector độ dài ~n-1~, mô tả đường ~i~ nối ~A[i]~ và ~B[i]~ (~0 \le A[i] < B[i] \le n-1~).

void Anya(vector<int> C)

Sau InitAnya, hàm này được gọi ~q~ lần (mỗi ngày 1 lần).

• C là vector độ dài ~n-1~.
• C[i] là 0/1: 1 nghĩa là đường ~i~ có tuyết, 0 nghĩa là đường ~i~ không có tuyết.

Trong Anya, được gọi hàm:

void Save(int place, int bit)

• place phải là số nguyên trong ~[0, l-1]~, sai -> Wrong Answer[1].
• Trong một lần gọi Anya, không được Save cùng một place quá 1 lần, nếu vi phạm -> Wrong Answer[2].
• bit phải là 0 hoặc 1, nếu sai -> Wrong Answer[3].
• Sau khi Save(place, bit), bit thứ place trên máy chủ bằng bit.

Trước mỗi lần Anya chạy, toàn bộ ~1000~ bit trên máy chủ được reset về 0. Nghĩa là bit nào Anya không Save thì cuối hàm vẫn là 0.

2) Namespace Boris

Cài đặt chiến lược của Boris, và phải có 2 hàm:

void InitBoris(int N, vector<int> A, vector<int> B)

Gọi đúng 1 lần mỗi test, tham số giống InitAnya.

int Boris(int city)

Được gọi nhiều lần sau InitBoris.

• city (~1 \le city \le n-1~): câu hỏi từ thành phố 0 đến city, tối thiểu phải đi qua bao nhiêu đường có tuyết?

• Trả về một số nguyên trong ~[0, n-1]~, sai phạm vi -> Wrong Answer[4].

• Nếu sai đáp án -> Wrong Answer[7].

Trong Boris, được gọi:

int Ask(int place)

• place phải trong ~[0, l-1]~, sai -> Wrong Answer[5].
• Mỗi lần gọi Boris, được gọi Ask tối đa ~20~ lần, vượt -> Wrong Answer[6].
• Ask(place) trả về bit (0/1) đang lưu ở vị trí đó trên máy chủ.

Trình tự chấm

• Gọi InitAnya, rồi InitBoris.
• Với mỗi ngày ~i = 1..q~:
  • Gọi Anya 1 lần để Anya lưu bit.
  • Gọi Boris tổng cộng ~D_i~ lần (số câu hỏi ngày ~i~), với tham số lần lượt là ~R_{i,1}, \dots, R_{i,D_i}~.
  • Nếu bất kỳ lần nào trả sai đáp án -> WA.
• Nếu không bị WA -> AC.

Lưu ý

• Anya/Boris không biết trước ~D_1, \dots, D_q~.

• Boris không biết khi nào Anya đã cập nhật dữ liệu máy chủ (chỉ biết qua dữ liệu đọc được).

• Khi chấm thực tế là 2 process, nên không thể chia sẻ biến toàn cục giữa Anya và Boris.

• Không được dùng stdin/stdout hay gọi hàm khác ngoài giao thức.

Ràng buộc

Mọi dữ liệu vào đều thoả mãn:

• ~2 \le n \le 500~
• ~1 \le q \le 500~
• ~0 \le A[i] < B[i] \le n-1~ với ~0 \le i \le n-2~
• ~1 \le D_j~ với ~1 \le j \le q~
• ~D_1 + \cdots + D_q \le 500~
• Với mọi cặp thành phố khác nhau, luôn tồn tại đường đi giữa hai thành phố đó.

Subtasks

Subtask 1 (15 điểm)

• ~n \le 20~

Subtask 2 (5 điểm)

• ~n \le 100~

Subtask 3 (35 điểm)

• ~A[i] = i~ với ~0 \le i \le n-2~
• ~B[i] = i + 1~ với ~0 \le i \le n-2~

Subtask 4 (45 điểm)

• Không có ràng buộc bổ sung.

Ví dụ

Dưới đây là một ví dụ input của grader mẫu và một chuỗi lời gọi hàm tương ứng.

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

Lưu ý: chuỗi lời gọi hàm trong bảng chỉ là ví dụ minh hoạ, không nhất thiết là lời gọi có ý nghĩa trong một lời giải đúng.

Trong ví dụ trên:

• InitAnya(...) và InitBoris(...) nhận:
  • ~n = 5~
  • A = [0, 1, 1, 2]
  • B = [1, 2, 4, 3]
• Lần gọi Anya(...) thứ nhất nhận C = [0, 1, 0, 1].
• Lần gọi Anya(...) thứ hai nhận C = [1, 1, 1, 0].

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á.

Trong bài này, bạn cần duy trì một multiset ~T~ mà mỗi phần tử của nó là một cặp ~(v_i, w_i)~. Ban đầu, ~T~ rỗng. Bạn cần thực hiện ~n~ thao tác, mỗi thao tác thuộc một trong ba loại sau:

• + v w với ~1 \le v \le 500000~, ~1 \le w \le n~: Chèn cặp ~(v, w)~ vào đa tập ~T~.

• - v w với ~1 \le v \le 500000~, ~1 \le w \le n~: Xóa một cặp ~(v, w)~ khỏi ~T~. Đảm bảo rằng cặp đó luôn tồn tại trong ~T~. Lưu ý ~T~ là một đa tập, nếu có nhiều bản sao của cùng một cặp, chỉ cần xóa đúng một bản.

• ? k với ~1 \le k \le 500000~: Đây là một truy vấn. Bạn cần tìm một cặp ~(v, w)~ trong ~T~ sao cho: ~ \gcd(v, k) = 1 ~ và trong tất cả những cặp thỏa điều kiện trên, giá trị ~w~ là lớn nhất.
Hãy in ra giá trị ~w~ đó. Nếu không tồn tại cặp phù hợp, hãy in -1.

Input

Chỉ có một test mỗi lần chạy.

Dòng đầu tiên chứa một số nguyên ~n~ (~1 \le n \le 200000~) — số lượng thao tác.

Mỗi dòng tiếp theo mô tả một thao tác theo đúng định dạng đã mô tả ở trên.

Output

Với mỗi truy vấn ? k, hãy in ra một dòng chứa giá trị ~w~ tương ứng, hoặc -1 nếu không tìm được.

Ví dụ

Input

6
+ 4 5
+ 3 4
? 2
? 3
- 3 4
? 4

Output

4
5
-1