Bài tập

In ra số nguyên \(42\).

Input

Không có dữ liệu đầu vào.

Output

Một dòng duy nhất chứa số \(42\).

Example

Nothing

42

\textitThis is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java --- System.out.flush(), in Pascal --- flush(output), and in Python --- sys.stdout.flush().

In this problem, the jury has some number \(x\), and you have to guess it. The number \(x\) is always an integer from \(1\) to \(n\), where \(n\) is given to you at the beginning.

You can make queries to the testing system. Each query is a single integer from \(1\) to \(n\). Flush the output stream after printing each query. There are two different responses the testing program can provide:

• the string "<" (without quotes), if the jury's number is less than the integer in your query;
• the string ">=" (without quotes), if the jury's number is greater than or equal to the integer in your query.

When your program guesses the number \(x\), print the string "! x", where \(x\) is the answer, and terminate your program normally immediately after flushing the output stream.

Your program is allowed to make no more than \(25\) queries (not including printing the answer) to the testing system.

Input

Use standard input to read the responses to the queries.

The first line contains an integer \(n\) (\(1 \le n \le 10^6\)) --- maximum possible jury's number.

Following lines will contain responses to your queries --- strings "<" or ">=". The \(i\)-th line is a response to your \(i\)-th query. When your program guesses the number, print "! x", where \(x\) is the answer, and terminate your program.

The testing system will allow you to read the response to the query only after your program prints the query for the system and performs the flush operation.

Output

To make the queries, your program must use standard output.

Your program must print the queries --- integer numbers \(x_i\) (\(1 \le x_i \le n\)), one query per line (do not forget "end of line" after each \(x_i\)). After printing each line, your program must perform the flush operation.

Each of the values \(x_i\) means the query to the testing system. The response to the query will be given in the input file after you flush the output. In case your program guesses the number \(x\), print the string "! x", where \(x\) --- is the answer, and terminate your program.

Example

12 20

Trong một buổi học về quản lý đô thị, lớp bạn An được thầy cho một bản quy hoạch giả tưởng về đường cao tốc của một quốc gia có \(n\) tỉnh thành được đánh số từ \(1\) tới \(n\) và \(n - 1\) đường cao tốc, trong đó đường cao tốc thứ \(i\) kết nối hai chiều giữa hai tỉnh \(u_{i}\) và \(v_{i}\) . Giữa hai tỉnh bất kỳ luôn được kết nối liên thông với nhau thông qua các đường cao tốc này. Các đường cao tốc này là tuyến huyết mạch quan trọng của cả đất nước, nên được xây vô cùng kiên cố và hoàn toàn không thể bị phá hủy bởi thiên tai.

Đất nước giả tưởng này cũng thường xuyên gặp động đất, vì vậy họ đã tạo ra một phương pháp đo lượng độ rung chấn, với thang đo có giá trị từ \(1\) tới \(10^9\). Ngoài ra, giả sử rằng khi có động đất, độ rung chấn ở mọi điểm trên mặt đất của toàn lãnh thổ là như nhau.

Để thuận tiện cho việc giao thông và giao thương giữa các tỉnh với nhau, giúp tăng sức bật cho nền kinh tế, Chính phủ giả tưởng quyết định xây thêm \(m\) đường cao tốc hai chiều nữa, trong đó đường thứ \(j\) kết nối tỉnh \(u_{j}\) với tỉnh \(v_{j}\) . Các tuyến đường phụ này có sức chịu tải kém hơn, nên khả năng chịu đựng rung chấn cũng kém hơn: con đường thứ \(j\) sẽ chịu được độ rung chấn tối đa là \(w_{j}\).

Khi quản trị rủi ro, chúng ta luôn phải tính tới nhiều phương án dự phòng khác nhau. Ví dụ, việc xây những tuyến đường huyết mạch cực kỳ kiên cố khiến cho động đất dù phá hủy đi \(k\) trong số \(m\) tuyến đường cao tốc phụ, thì \(n - 1\) tuyến đường huyết mạch vẫn có khả năng kết nối giao thông của toàn quốc, và \(m - k\) tuyến đường còn lại sẽ chịu tải một phần cho những tuyến đường gốc này. Thêm nữa, \((n - 1) + (m - k)\) con đường còn lại tuy là không bị chặn, nhưng mà động đất khiến những con đường dễ bị nứt vỡ cục bộ, nên cần phải lần lượt bảo trì. Mà mỗi khi bảo trì thì xe không được lưu thông trên đường cao tốc. Vì vậy, nếu có một con đường trong giai đoạn bảo trì, thì \((n - 1) + (m - k) - 1\) con đường còn lại vẫn phải đảm bảo kết nối giao thông giữa hai tỉnh thành bất kỳ với nhau.

Sau khi trình bày xong vấn đề nêu trên, thầy giáo đưa ra yêu cầu cho các bạn sinh viên là hãy tính độ chống chịu của giao thông đất nước này. Độ chống chịu là giá trị \(w\) lớn nhất, sao cho khi động đất \(w\) độ xảy ra trên toàn quốc, thì cho dù một số đường cao tốc bị sập, những đường cao tốc còn lại vẫn phải đảm bảo kết nối được hai tỉnh thành bất kỳ với nhau, kể cả trong trường hợp có thêm tối đa một con đường cần phải bảo trì.

Để tạo ra nhiều bài tập cho các bạn về nhà luyện tập, thầy quyết định cho các bạn thêm \(q\) phiên bản quy hoạch nữa. Gọi phiên bản gốc (phiên bản thứ \(0\)) là phiên bản gồm \((n - 1) + m\) đường cao tốc ban đầu; phiên bản thứ \(y\) được tạo bằng cách thêm vào phiên bản thứ \(y - 1\) một tuyến đường cao tốc phụ nữa nối giữa tỉnh \(u′_{y}\) và tỉnh \(v′_{y}\), với khả năng chống chịu động đất tối đa \(w′_{y}\) độ. Hãy tính độ chống chịu của quốc gia này ở mỗi phiên bản quy hoạch trong số \(q + 1\) phiên bản.

Input

Dòng dầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 15 \times 10^4)\) là số tỉnh thành trong nước.

Dòng thứ \(i\) trong số \(n - 1\) dòng tiếp theo chứa hai số nguyên \(u_{i}\) và \(v_{i}\) \((1 \leq u_{i} , v_{i} ≤ n, u_{i} \neq v_{i})\) thể hiện một đường cao tốc huyết mạch nối giữa hai thành phố \(u_{i}\) và \(v_{i}\). Dữ liệu đảm bảo tồn tại một đường đi giữa hai thành phố bất kỳ mà chỉ dùng những cây cầu này.

Dòng tiếp theo chứa một số nguyên \(m\) \((0 \leq m \leq 2 \times 10^5)\) là đường cao tốc đã được xây thêm.

Dòng thứ \(j\) trong số \(m\) dòng tiếp theo chứa hai số nguyên \(u_{j} , v_{j}\) và \(w_{j}\) \((1 \leq u_{j} , v_{j} \leq n, u_{j} \neq v_{j} , 1 \leq w_{j} \leq 10^9)\) thể hiện một tuyến đường cao tốc phụ đã được xây thêm giữa hai thành phố \(u_{j}\) và \(v_{j}\) với khả năng chịu rung chấn tối đa \(w_{j}\) độ.

Dòng tiếp theo chứa một số nguyên \(q\) \((0 \leq q \leq 3 \times 10^5)\) là số phiên bản quy hoạch mà giảng viên giao cho.

Dòng thứ \(y\) trong số \(q\) dòng tiếp theo chứa ba số nguyên \(u′_{y}\), \(v′_{y}\) và \(w′_{y}\) \((1 \leq u′_{y}, v′_{y} \leq n, u′_{y} \neq v′_{y}, 1 \leq w′_{y} \leq 10^9)\) thể hiện một tuyến đường phụ sẽ được xây thêm giữa hai thành phố \(u′_{y}\) và \(v′_{y}\) với khả năng chịu rung chấn tối đa \(w\) độ.

Output

In ra \(q + 1\) dòng, dòng thứ \(i\) \((1 \leq i \leq q + 1)\) chứa một số nguyên là độ chống chịu của quốc gia đó tại phiên bản quy hoạch thứ \(i - 1\). Nếu với mọi trận động đất với sức mạnh khác nhau, ta luôn tìm được một cây cầu mà khi bảo trì thì các tỉnh thành còn lại không liên thông với nhau, thì phiên bản quy hoạch đấy không có sức chống chịu rủi ro, khi đó ta in ra \(−1\).

Example

4
1 2
1 3
1 4
2
2 3 4
3 4 5
0

4

5
1 2
2 3
2 4
3 5
2
1 4 3
3 1 2
1
2 5 4

-1
3

Scoring

Subtask \(1\) (\(15\%\) số điểm): \(n \leq 500\), \(m = 1\), \(q = 0\) và mỗi tỉnh kề với không quá \(2\) đường cao tốc trong số \(n − 1\) đường cao tốc thuộc bản quy hoạch giả tưởng.

Subtask \(2\) (\(14\%\) số điểm): \(n, m \leq 500\), \(q = 0\).

Subtask \(3\) (\(8\%\) số điểm): \(n, m, q \leq 500\).

Subtask \(4\) (\(9\%\) số điểm): \(n \leq 3000, m \leq 5000, q = 0\).

Subtask \(5\) (\(12\%\) số điểm): \(n \leq 8000\), \(m \leq 7000\), \(q \leq 9000\).

Subtask \(6\) (\(15\%\) số điểm): \(q = 0\).

Subtask \(7\) (\(17\%\) số điểm): Mỗi tỉnh kề với không quá \(2\) đường cao tốc trong số \(n - 1\) đường cao tốc thuộc bản quy hoạch giả tưởng.

Subtask \(8\) (\(10\%\) số điểm): Không có ràng buộc gì thêm.

Đất nước Z có \(n\) thành phố, các thành phố được đánh số từ \(1\) đến \(n\) và được nối với nhau bởi \(n - 1\) con đường để đảm bảo đi lại giữa hai thành phố bất kỳ. Mức độ phát triển của thành phố \(i\ (1 \le i \le n)\) là \(p_i\). Chính phủ thực hiện một dãy gồm \(q\) các công việc thuộc một trong hai loại sau:

• Loại \(1\) có dạng \(1\ i\ x\), nghĩa là đầu tư vào thành phố \(i\ (1 \le i \le n)\) để tăng mức độ phát triển của thành phố \(i\) thêm \(2x\), mức độ phát triển của các thành phố liền kề \(i\) cũng được tăng thêm \(x\).

• Loại \(2\) có dạng \(2\ i\), nghĩa là tính độ hưng thịnh của cụm các thành phố khi lấy \(i\) làm trung tâm, giá trị này được tính bằng mức độ phát triển của thành phố \(i\) và tất cả các thành phố kề \(i\).

Yêu cầu: Với mỗi công việc loại \(2\) đưa ra giá trị cần tính.

Input

• Dòng đầu chứa hai số nguyên \(n, q\ (n \le 3 \times 10^5; q \le 3 \times n)\).
• Dòng tiếp theo là \(n\) số nguyên không âm \(p_1, p_2, \ldots, p_n\ (p_i \le 10^9)\).
• Tiếp theo là \(n - 1\) dòng, mỗi dòng là một cặp số nguyên \(u, v\) mô tả có con đường nối thành phố \(u\) với thành phố \(v\).
• Tiếp theo là \(q\) dòng, mỗi dòng mô tả công việc mà chính phủ thực hiện.

Output

• Với mỗi công việc loại \(2\), đưa ra giá trị cần tính.

Example

3 5
0 0 0
1 2
2 3
1 1 1
1 2 2
2 1
2 2
2 3

9
11
7