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~:

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

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