Thời gian rảnh Thuận thường hướng dẫn các em nhỏ học lập trình, dưới đây là một bài toán rèn luyện kĩ năng cũng như tư duy lập trình.

Cho một dãy số nguyên dương \(a_1, a_2, ..., a_n (1 < a_i \le 10^9)\) và số nguyên dương \(t (1 \le t \le 3)\). Gọi \(s_1, s_2, s_3\) tương ứng là số bộ chỉ số \(1 \le i < j < k \le n\) mà \(a_i, a_j, a_k\) là ba cạnh của một tam giác nhọn, tam giác vuông, tam giác tù. Hãy tính giá trị \(s_t\).

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

• Dòng đầu chứa hai số nguyên dương \(n, t\);
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, ..., a_n\).

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là giá trị \(s_t\) tính được.

Scoring

• Subtask #1 (\(30\%\) số điểm): \(n = 3\) và 10% cho từng giá trị của \(t\);
• Subtask #2 (\(30\%\) số điểm): \(n \le 300\) và 10% cho từng giá trị của \(t\);
• Subtask #3 (\(40\%\) số điểm): \(n \le 3000\)

Example

3 2
3 4 5

1

4 1
3 4 5 6

1