Đây là một bài toán tương tác.

Menji bị lạc và mọi người đều nhớ anh ấy. Nhiệm vụ của bạn là tìm ra anh ấy!

Có một cây nhị phân $T$ gồm $n$ đỉnh, và mỗi cạnh của cây $T$ có độ dài bằng $1$. Menji đang trốn tại đỉnh $X$. Bạn biết cấu trúc của cây, nhưng bạn không biết $X$.

Để tìm $X$, bạn có thể gửi tín hiệu. Bạn có thể chọn một đỉnh $u$ và chọn cường độ tín hiệu $k$, sau đó gửi một tín hiệu có cường độ $k$ từ đỉnh $u$. Nếu khoảng cách giữa $u$ và $X$ không vượt quá $k$, Menji sẽ nhận được tín hiệu và gửi phản hồi lại, và bạn sẽ nhận được tín hiệu đó. Ngược lại, bạn sẽ không nhận được gì cả.

Việc gửi tín hiệu rất chậm và bạn đang vội, vì vậy hãy xác định vị trí của Menji với không quá $40$ lần gửi tín hiệu.

Giao thức tương tác

Dữ liệu vào gồm nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 100$), là số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên $n$ ($2 \le n \le 3 \times 10^4$), là số lượng đỉnh trong cây.

Dòng thứ hai chứa $n - 1$ số nguyên $fa_2, fa_3, \dots, fa_n$ ($1 \le fa_i < i$), trong đó $fa_i$ là cha của đỉnh $i$ trên cây. Cây có gốc tại đỉnh $1$.

Dữ liệu đảm bảo cây là cây nhị phân, tức là không tồn tại $1 < i < j < k \le n$ sao cho $fa_i = fa_j = fa_k$.

Để gửi một tín hiệu, hãy in ra một dòng duy nhất theo định dạng sau:

• ? u k: Cho biết bạn phát một tín hiệu tại đỉnh $u$ với cường độ $k$. Bạn cần đảm bảo $1 \le u \le n, 0 \le k \le n$. Sau đó bạn phải đọc một số nguyên $o$ ($o \in \{0, 1\}$). Nếu bạn nhận được tín hiệu, hay tương đương với $dis(u, X) \le k$, thì $o = 1$, ngược lại $o = 0$.

Để báo cáo đáp án, hãy in ra một dòng duy nhất theo định dạng sau:

• ! u: Cho biết bạn đã tìm ra $X = u$. Sau khi in dòng này, bạn cần chuyển sang bộ dữ liệu tiếp theo, hoặc kết thúc chương trình nếu không còn bộ dữ liệu nào nữa.

Đối với mỗi bộ dữ liệu, bạn có thể gửi tối đa $40$ tín hiệu. Việc báo cáo đáp án không được tính là một lần gửi tín hiệu.

Nếu bạn gửi quá $40$ tín hiệu, hoặc tín hiệu bạn gửi sai định dạng, hoặc đáp án bạn báo cáo không chính xác, quá trình tương tác sẽ kết thúc và bạn sẽ nhận kết quả Wrong answer.

Lưu ý rằng trình tương tác có tính thích ứng (adaptive), nghĩa là đáp án có thể thay đổi tùy thuộc vào các truy vấn của bạn miễn là nó vẫn nhất quán với các ràng buộc và các câu trả lời cho những truy vấn trước đó.

Dữ liệu đảm bảo tổng của $n$ qua tất cả các bộ dữ liệu không vượt quá $3 \times 10^4$.

Sau khi in mỗi dòng, đừng quên in ký tự xuống dòng và làm rỗng bộ đệm đầu ra (flush). Bạn có thể sử dụng fflush(stdout) hoặc cout.flush() trong C++, System.out.flush() trong Java và stdout.flush() trong Python.

Ví dụ

Dữ liệu vào mẫu 1

2
7
1 1 2 2 3 3

1

0

0

7
1 1 2 2 3 3

0

1

Dữ liệu ra mẫu 1

? 2 1

? 3 2

? 4 0

! 5

? 2 1

? 3 0

! 3