Anh có ~n~ món đồ chơi được đánh số từ ~1..n~, món hàng thứ ~i~ có giá trị là ~i~. Anh bắt đầu gói những món đồ chơi của mình thành từng phần quà để gửi tặng đến những người em của mình. Mỗi phần quà phải có giá trị giống nhau và bằng ~k~.

Anh muốn biết mình có thể gói được nhiều nhất là bao nhiêu phần quà để tặng được nhiều người em nhất.

Input Specification

• Một dòng duy nhất bao gồm hai giá trị ~n~ và ~k~ tương ứng là số món đồ chơi và giá trị phần quà mà Anh muốn.

Output Specification

• Gồm một số nguyên duy nhất là số phần quà nhiều nhất mà Anh gói được.

Constrains

• ~1 \le n, k \le 10^{14}~

Sample Cases

Input #1:

8 5

Output #1:

2

Input #2:

8 15

Output #2:

1

Vừa mới đi làm trở lại sau Tết, Khoa đã bị sếp giao một công việc vô cùng hóc búa: Công ty của Khoa còn tồn đọng ~N~ sản phẩm từ năm ngoái, sản phẩm thứ ~i~ có chủng loại là ~c_i~. Do đặc thù kỹ thuật, các sản phẩm này không thể bán lẻ mà phải bán theo bộ ~2~ hoặc ~3~ sản phẩm cùng chủng loại. Để giải quyết số hàng tồn đọng nhanh nhất có thể, sếp muốn Khoa chia ~N~ sản phẩm này thành ít nhất có thể các bộ ~2~ hoặc ~3~ sản phẩm cùng chủng loại.

Sau những ngày nghỉ Tết chỉ biết ăn và ngủ, đầu óc Khoa bây giờ không còn khả năng "nhảy số" nhanh nhẹn như trước nữa. Cậu chỉ biết nghĩ về những món ăn ngon mà mình đã ăn trong những ngày nghỉ Tết. Nhưng công việc sếp giao thì bắt buộc phải hoàn thành ngay hôm nay, nếu không sếp sẽ đuổi việc Khoa!

Bị đuổi việc đầu năm quả là điều không may mắn chút nào. Các bạn hãy giúp Khoa hoàn thành công việc sếp giao nhé.

Input Specification

• Dòng đầu tiên chứa số nguyên dương ~N~ là số lượng sản phẩm tồn đọng.
• Dòng thứ hai chứa ~N~ số nguyên ~c_1, c_2, \dots, c_N~ là chủng loại của các sản phẩm.

Output Specification

• In ra một số nguyên duy nhất là số bộ sản phẩm ít nhất có thể.
• Nếu không tồn tại cách chia, in ra -1.

Constrains

• ~1 \le N \le 10^5~
• ~1 \le c_i \le 10^9~

Sample Cases

Input #1:

10
2 2 3 3 2 4 4 4 4 4

Output #1:

4

Input #2:

3
2 3 3

Output #2:

-1

Explanation #1, #2

• Ở ví dụ thứ nhất, chia thành ~4~ bộ sản phẩm: ~\{2, 2, 2\}, \{3, 3\}, \{4, 4, 4\}, \{4, 4\}~.
• Ở ví dụ thứ hai, không có cách chia nào do chỉ có một sản phẩm có chủng loại ~2~.

Nhân dịp các bạn lớp 11A1 đi học trở lại sau Tết, vì có một số bạn chưa làm bài tập Tết nên thầy Phú quyết định đưa ra hình phạt như sau: Nếu một bạn bất kì không làm bài tập Tết thì số điểm cộng của các bạn khác trong lớp sẽ được cộng thêm 1 đơn vị.

Yêu cầu: Cho số lượng học sinh trong lớp, danh sách điểm cộng trước Tết của các bạn và số bạn chưa làm bài tập Tết. Đưa ra danh sách điểm cộng mới của các bạn lớp 11A1.

Input Specification

• Dòng thứ nhất ghi hai số nguyên dương ~n, k~ - số lượng học sinh trong lớp và số học sinh không làm bài tập Tết.
• Dòng thứ hai chứa dãy ~a_1, a_2, \dots, a_n~ - điểm cộng của các bạn lớp 11A1 trước Tết.
• Tiếp theo là ~k~ dòng, dòng thứ ~i~ chứa số nguyên ~K_i~ - thứ tự của bạn học sinh không làm bài tập Tết.

*Dữ liệu đảm bảo danh sách các bạn không làm bài tập tết là đôi một khác nhau.

Output Specification

• In ra danh sách điểm cộng mới trên một dòng.

Constrains

• ~1 \le n, k \le 2 \cdot 10^5~
• ~1 \le a_i \le 10^6~
• ~1 \le K_i \le n~

Sample Cases

Input #1:

6 4
3 5 3 1 7 8
3
4
5
1

Output #1:

6 9 6 4 10 12

Cho dãy số $A$ gồm có $n$ số nguyên dương ~\{ A_1, A_2, \dots, A_n \}~.

Hãy cho biết có bao nhiêu giá trị xuất hiện ít nhất ~k~ lần trong dãy ~A~, tổng của các giá trị khác nhau đó?

Input Specification

• Dòng đầu tiên chứa hai số ~n~.
• Dòng tiếp theo lần lượt chứa ~n~ số ~A_1, A_2, \dots, A_n~.

Output Specification

• In ra một dòng duy nhất chứa hai số, lần lượt là số lượng giá trị xuất hiện ít nhất ~k~ lần trong dãy ~A~, và tổng của ~k~ giá trị đó.

Constrains

• ~1 \le n, k \le 10^5~
• ~1 \le A_i \le 10^9~

Sample Cases

Input #1:

6 2
3 1 2 3 2 5

Output #1:

2 5

Explanation #1:

• Ở test ví dụ trên, ~n = 6, k = 2~. Dãy ~A~ có một phần tử giá trị ~1~, hai phần tử giá trị ~2~, hai phần tử giá trị ~3~ và một phần tử giá trị ~5~.
• Vì thế, có ~2~ giá trị thỏa mãn là ~2~ và ~3~, tổng của chúng là ~5~.

Cho một dãy ~n~ số nguyên ~a_1, a_2, \dots, a_n~ và ~m~ truy vấn ~l_j, r_j~ ~(1 \le l_j \le r_j \le n)~. Với mỗi truy vấn, bạn cần tìm khoảng cách nhỏ nhất giữa hai phần tử ~a_x~ và ~a_y~ sao cho:

• Cả hai phần tử đều nằm trong đoạn ~[l_j, r_j]~ ~(l_j \le x, y \le r_j)~.
• Hai phần tử đều có giá trị bằng nhau ~(a_x = a_y)~.

Input Specification

• Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~m~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_i~.
• ~m~ dòng tiếp theo gồm các truy vấn, mỗi truy vấn gồm hai số nguyên dương ~l_i, r_i~.

Output Specification

• Gồm ~m~ dòng, trong đó dòng thứ ~i~ là khoảng cách ~|x - y|~ nhỏ nhất tìm được trong truy vấn thứ ~i~. Nếu không có cặp nào thỏa điều kiện thì in ra -1.

Subtasks

• Subtask 1 [20%]: ~1 \le n, m \le 100~.
• Subtask 2 [20%]: ~1 \le n, m \le 1000~.
• Subtask 3 [60%]: Không có ràng buộc gì thêm.

Constrains

• ~1 \le n, m \le 5 \cdot 10^5~
• ~-10^9 \le a_i \le 10^9~
• ~1 \le l_i \le r_i \le n~

Sample Cases

Input #1:

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

Output #1:

2
-1
1

Input #2:

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

Output #2:

2
3
2
2
-1