Xác Suất Cùng Màu

Cho một dãy gồm $n$ màu. Mỗi truy vấn chọn một đoạn đóng $[l,r]$. Từ tất cả các cặp không có thứ tự gồm hai vị trí khác nhau trong đoạn, ta chọn đều ngẫu nhiên một cặp. Hãy tính xác suất hai vị trí được chọn có cùng màu.

Kết quả phải được viết dưới dạng phân số tối giản $p/q$. Nếu đoạn có ít hơn hai vị trí hoặc không có cặp cùng màu, quy ước kết quả là $0/1$.

Input

• Dòng đầu chứa hai số nguyên $n$ và $q$ - số phần tử của dãy và số truy vấn.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ - màu tại từng vị trí.
• Mỗi trong $q$ dòng tiếp theo chứa hai số nguyên $l$ và $r$.

Output

• Với mỗi truy vấn, in trên một dòng phân số tối giản $p/q$ biểu diễn xác suất cần tìm.

Constraints

• $1\le n,q\le 5\cdot 10^4$.
• $1\le a_i\le n$ với mọi $i$.
• $1\le l\le r\le n$ với mọi truy vấn.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 2000$ và $q\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

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

4/15
1/3
0/1
0/1