Bài tập

Cho một cái cây có \(n\) nút và ta định nghĩa \(1\) là nút gốc của cây.

Bây giờ ta có \(q\) truy vấn, mỗi truy vấn có dạng: \(l_{i}\) \(r_{i}\) (\(1 \leq l_{i} \leq r_{i} \leq n\)).

Yêu cầu: Ứng với mỗi truy vấn, ta in ra LCA của tất cả các nút từ nút \(l_{i}\) đến nút \(r_{i}\)

Input

• Dòng thứ nhất chứa số n (\(2 \leq n \leq 300000\)) - Thể hiện số nút của cây

• \(n−1\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(x,y\) - Thể hiện cạnh nối giữa hai đỉnh \(x\) và \(y\)

• Dòng tiếp theo, chứa số \(q\) (\(1 \leq q \leq 300000\)) - Thể hiện số lượng truy vấn

• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l_{i}\), \(r_{i}\) (\(1 \leq l_{i} \leq r_{i}\leq n\))

Output

• Ứng với mỗi truy vấn, in ra đáp án cần tìm.

Example

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

4
1

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(2 \leq n,q \leq 20\).

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

You are given a sequence of integers of length \(n\) and integer number \(k\). You should print any integer number \(x\) in the range of \([1; 10^9]\) (i.e. \(1 \le x \le 10^9\)) such that exactly \(k\) elements of given sequence are less than or equal to \(x\).

Note that the sequence can contain equal elements.

If there is no such \(x\), print "-1" (without quotes).

Input

The first line of the input contains integer numbers \(n\) and \(k\) (\(1 \le n \le 2 \cdot 10^5\), \(0 \le k \le n\)).
The second line of the input contains \(n\) integer numbers \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) --- the sequence itself.

Output

Print any integer number \(x\) from range \([1; 10^9]\) such that exactly \(k\) elements of given sequence is less or equal to \(x\).

If there is no such \(x\), print "-1" (without quotes).

Example

7 4
3 7 5 1 10 3 20

7 2
3 7 5 1 10 3 20

Tutorial

In this problem you can do the following thing: firstly, let's sort our array.

Let \(ans\) will be the answer. Then you have two cases: if \(k = 0\) then \(ans := a_0 - 1\) otherwise \(ans := a_{k - 1}\) (for 0-indexed array).

Then you need to calculate the number of the elements of the array \(a\) that are less than or equal to \(ans\). Let it be \(cnt\). Then if \(ans < 1\) or \(cnt \ne k\) then print "-1" otherwise print \(ans\).

Lớp \(11\) chuyên Tin có \(n\) học sinh, thầy chủ nhiệm Linh Phan muốn chọn ra một số bạn ở lại trực nhật lớp. Để thêm tính hấp dẫn và công bằng, thầy viết một đoạn code cấp cho mỗi bạn một số tự nhiên ngẫu nhiên và quy định rằng, nếu bạn nào nhận được số có tổng các ước dương của nó nhỏ hơn hai lần số đó thì phải đi trực nhật.

Một lần không may mắn, máy tính của thầy Linh Phan đã sinh ra các số mà sau khi cấp phát cho học sinh thì không có học sinh nào phải ở lại trực nhật. Rút kinh nghiệm từ lần đó, thầy đã chuẩn bị sẵn một dãy số, rồi nhờ các em đội tuyển Tin tính xem có bao nhiêu số có tổng các ước dương nhỏ hơn hai lần số đó, nếu số lượng số này đủ nhiều thì thầy sẽ lấy dãy số đó để cấp cho các bạn trong lớp.

Yêu cầu: Cho số nguyên dương \(n\) và dãy số \(a_1\), \(a_2\),..., \(a_{n -- 1}\), \(a_n\). Hãy giúp thầy Linh Phan xác định xem với dãy số này thì có bao nhiêu em học sinh phải làm nhiệm vụ trực nhật.

Input

• Dòng đầu ghi số nguyên dương \(n\), số học sinh trong lớp.

• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1\), \(a_2\),..., \(a_{n--1}\), \(a_n\).

• \(N\leq 10^6\)

• \(a_i\leq 5.10^6\)

Output

• Gồm một số duy nhất là số học sinh phải ở lại trực nhật tương ứng với dãy số input.

Example

5
3 6 9 12 9

3

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(N\leq 10^3, a_i\leq 10^4\)

• Subtask \(2\) (\(15\%\) số điểm): \(N\leq 10^4, a_i\leq 5.10^6\)

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

Cho dãy \(A\) gồm \(N\) số nguyên dương \(a_{1}, a_{2}, … ,a_{N}\) và một số nguyên dương \(K\) . Một đoạn con của \(A\) là một dãy liên tục các phần tử của \(A\). Một đoạn con của \(A\) được gọi là hài hòa nếu trung bình cộng của các phần tử trong đoạn con đó đúng bằng \(K\).

Yêu cầu: Hãy tìm đoạn con hài hòa dài nhất bằng cách chỉ ra độ dài và chỉ số phần tử đầu tiên của đoạn con đó. Nếu tồn tại nhiều đoạn con như vậy thì đưa ra đoạn con có chỉ số của phần tử đầu tiên nhỏ nhất. Nếu không tồn tại đoạn con nào thỏa mãn thì ghi ra số \(0\).

Input

Đọc từ tệp văn bản BAI4.INP có cấu trúc:

--- Dòng đầu tiên ghi hai số nguyên dương \(N\) và \(K\) \((1 ≤ N ≤ 10^5), 1 ≤ K ≤ 10^9)\);

--- Dòng thứ hai chứa \(N\) số nguyên \(a_{1}, a_{2}, … ,a_{N}\) \((1 ≤ a_{i} ≤ 10^9, i = 1, 2, … , N)\);

--- Các số cách nhau một dấu cách.

Output

Ghi ra tệp văn bản BAI4.OUT hai số nguyên dương là độ dài và chỉ số phần tử đầu tiên của đoạn con tìm được, các số ghi trên một dòng và cách nhau một dấu cách hoặc ghi ra số \(0\) nếu không tồn tại đoạn con nào thỏa mãn điều kiện của bài toán.

Example

5 3
1 2 3 4 6

3 2

4 3
1 2 5 6

0

Scoring

--- Có \(30\%\) số test tương ứng với \(30\%\) số điểm có \(N ≤ 100\).

--- Có \(60\%\) số test tương ứng với \(60\%\) số điểm có \(N ≤ 5000\).

--- \(10\%\) còn lại không có ràng buộc gì thêm.

--- Thời gian thực hiện mỗi test không quá một giây.