Ở mùa giải ICPC 2025 mới, nhân lực của CLB lập trình của UMT rất đông và hung hãn. Năm nay kỳ thi ICPC cấp khu vực sẽ tổ chức tại TP.HCM nên không có lý do gì mà UMT không huy động nhân lực để tham gia được nhiều team càng nhiều càng tốt.

Trong CLB hiện tại có tất cả ~n~ thành viên và sau quá trình dài tham gia thi trên codeforces.com cũng như nhiều nên tảng khác thì thầy Trung chủ nhiệm CLB đánh giá rằng mỗi người có một điểm số năng lực nhất định (tất nhiên có thể có nhiều người có cùng điểm số năng lực). Thầy Trung muốn các bạn tạo với nhau thành các team ba người, trong đó hai thành viên bất kỳ cùng team thì chênh lệch điểm số năng lực không quá 2 đơn vị. Hãy giúp thầy Trung đếm xem có tất cả bao nhiêu cách khác nhau để tạo team theo ràng buộc trên nhé.

Input

Dòng đầu tiên gồm số nguyên dương ~n~ với ~3 ≤ n ≤ 10^5~.

Dòng tiếp theo gồm điểm số năng lực của các thành viên, có giá trị nguyên dương không vượt quá ~10^9~

Output

Số team có thể tạo thành.

Sample Input 1

4
11 12 13 14

Sample Ouput 1

2

Sample Input 2

5
1 1 1 1 1

Sample Ouput 2

10

Giải thích

Trong Ví dụ 1, ta thấy các bạn có số thứ tự (1, 2, 3) và (2, 3, 4) có thể cùng team với nhau; còn trong Ví dụ 2, ta thấy ba bạn bất kỳ đều có thể tạo thành team, số cách chọn là ~C_{5}^{3}=10~.

Subtask:

• Subtask 1 (50% số điểm): ~n ≤ 10~.

• Subtask 2 (50% số điểm): Không giới hạn gì thêm.

Trong một buổi sinh hoạt học thuật tại UMT, các thành viên được giao nhiệm vụ làm sạch một tập dữ liệu đầu vào bị trùng lặp. Mỗi bạn được cấp một dãy số gồm n phần tử nguyên, đại diện cho các mã sinh viên do hệ thống ghi nhận (nhưng đôi khi bị lỗi lặp mã).

Để chuẩn bị cho một buổi phân tích tiếp theo, cố vấn học thuật yêu cầu mỗi bạn phải làm sạch dãy mã sinh viên này sao cho mọi mã còn lại đều khác nhau (không có mã nào trùng lặp). Tuy nhiên, do hạn chế giao diện phần mềm, mỗi thao tác chỉ có thể là:

• Xóa mã đầu tiên trong danh sách.

• Xóa mã cuối cùng trong danh sách.

Nhiệm vụ của bạn là xác định số thao tác ít nhất cần thực hiện để danh sách chỉ còn các mã phân biệt.

Input

Dòng đầu tiên là một số nguyên n ~(1 ≤ n ≤ 10^5)~ — số lượng mã sinh viên được ghi nhận.

Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, . . . , a_n (1 ≤ a_i ≤ 10^5)~ — danh sách mã sinh viên.

Output

In ra một số nguyên duy nhất — số thao tác tối thiểu cần thực hiện để danh sách trở nên phân biệt.

Sample Input 1

4
4 3 3 2

Sample Ouput 1

2

Sample Input 2

5
1 2 3 4 5

Sample Ouput 2

0

Giải thích

Trong test mẫu trên, bạn có thể xóa hai phần tử đầu tiên để được dãy [3, 2], hoặc hai phần tử cuối cùng để được [4, 3]. Cả hai đều là dãy gồm các phần tử phân biệt, và cần đúng 2 thao tác.

Subtask:

• Subtask 1 (50% số điểm): ~n ≤ 5000~

• Subtask 2 (50% số điểm): Không giới hạn gì thêm.

Trong một dự án nghiên cứu tại Trung tâm Công nghệ UMT, bạn được giao nhiệm vụ tối ưu hóa năng lượng trong một hệ thống gồm n thiết bị điện tử. Mỗi thiết bị có một mức năng lượng ban đầu, được biểu diễn bằng một số nguyên không âm. Bạn có thể thực hiện các thao tác sau bất kỳ số lần nào:

• Chọn hai thiết bị khác nhau, ký hiệu là ~i~ và ~j~.

• Cập nhật mức năng lượng của thiết bị ~i~ thành ~a_i ← a_i~ AND ~a_j~ (phép AND bitwise).

• Cập nhật mức năng lượng của thiết bị ~j~ thành ~a_j ← a_i~ OR ~a_j~ (phép OR bitwise).

Sau khi thực hiện các thao tác, bạn cần chọn ra k thiết bị và tính tổng bình phương mức năng lượng của chúng. Mục tiêu là tối đa hóa tổng này. Do kết quả có thể rất lớn, hãy in ra tổng bình phương mức năng lượng lớn nhất có thể đạt được, lấy MOD~10^9+7~.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ ~(1 ≤ k ≤ n ≤ 10^5)~ — số lượng thiết bị và số thiết bị cần chọn.

Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, . . . , a_n (0 ≤ a_i < 2^30)~ — mức năng lượng ban đầu của các thiết bị.

Output

In ra một số nguyên duy nhất — tổng bình phương mức năng lượng lớn nhất có thể đạt được sau các thao tác, MOD ~10^9 + 7~.

Sample Input 1

3 2
3 8 2

Sample Ouput 1

125

Sample Input 2

3 3
1 3 5

Sample Ouput 2

51

Subtask:

• Subtask 1 (10% số điểm): ứng với ~n ≤ 10^4~

• Subtask 2 (90% số điểm): không giới hạn gì thêm.

Để tham gia được tại sân chơi rộng lớn là OLP-ICPC, các chiến binh của UMT đã khổ luyện ngày đêm. Ngoài việc tham gia các khoá học online, các bạn còn cùng nhau tổ chức các chương trình codecamp thật bổ ích. Vậy đó là gì?

Codecamp là một hoạt động không thể thiếu của các coder competitive programming tại UMT. Đó là dịp mà các bạn sẽ tách khỏi trường, đi đến một nơi thật xa, và chỉ để code. Có lần thì đi ra cảng Cát Lái ngắm hoàng hôn, có lần đi Vũng Tàu bắt cá, hoặc ra tận Huế để để vừa ngắm sông Hương vừa code, ... Và trong một chuyến codecamp như thế của CLB lập trình UMT, các thành viên thuê xe máy để đi tham quan các địa điểm. Có tất cả ~n~ địa điểm để thăm và giữa chúng có ~m~ con đường một chiều cho xe máy chạy qua được (nghĩa là có đường đi từ ~A~ đến ~B~ thì chưa chắc có đường từ ~B~ về ~A~), trong đó có ~k~ địa điểm có phục vụ ăn uống. Các coder của UMT muốn xen kẽ giữa chuyến đi chơi sẽ có các buổi ăn uống, thư giãn. Vì thế các coder muốn biết rằng từ mỗi địa điểm trong ~n~ địa điểm thì khoảng cách ngắn nhất đến một địa điểm ăn uống nào đó là bao nhiêu (khoảng cách ở đây là số con đường một chiều mà bạn ấy cần phải đi qua).

Input

Dòng đầu tiên gồm các số ~n~, ~m~, ~k~ cho biết số địa điểm, số đường đi và số địa điểm đặc biệt, trong đó ~2 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^6~ (các đường đi có thể bị lặp lại) và ~0 ≤ k ≤ n~. Dòng thứ hai gồm danh sách các địa điểm ăn uống, mỗi giá trị sẽ từ 1 đến ~n~, phân biệt nhau. Trong m dòng tiếp theo sẽ có các thông tin con đường đi giữa từ địa điểm ~u → v~ nào đó với ~1 ≤ u \neq v ≤ n~

Output

Một dòng duy nhất gồm n khoảng cách từ địa điểm 1, 2, ..., ~n~ đến chỗ có thể ăn uống gần nhất. Với mỗi địa điểm không đi được thì in ra -1.

Sample Input 1

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

Sample Ouput 1

0 3 2 1 0

Sample Input 2

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

Sample Ouput 2

0 1 -1 -1 0

Giải thích

Trong Ví dụ 1, ta thấy địa điểm 1, 5 đã là đặc biệt nên không cần di chuyển gì, còn từ địa điểm 2, 3, 4 có thể đi đến địa điểm 5 với độ dài đường đi lần lượt là 3, 2, 1; trong Ví dụ 2, ta thấy tương tự trên nhưng địa điểm 2 đến được địa điểm 1 qua 1 bước, còn địa điểm 3, 4 thì không đến được 1 hoặc 5 bằng cách nào cả..

Subtask:

• Subtask 1 (50% số điểm): ứng với ~n ≤ 10~.

• Subtask 2 (15% số điểm): ứng với ~10 < n ≤ 1000~.

• Subtask 3 (35% số điểm): Không giới hạn gì thêm.