Description

Updated on 2020.6.10: time limit updated.

As a somewhat careless person, Xiao Z spends a long time every morning trying to find a pair of socks from a pile of colorful ones. One day, he could no longer stand this annoying process and decided to leave it to fate.

Specifically, Xiao Z numbers his $N$ socks from $1$ to $N$, then randomly selects two socks to wear from those numbered $L$ to $R$. Although Xiao Z does not care whether the two socks form a true pair, he does care about their colors, since wearing two socks of different colors would be embarrassing.

Your task is to tell Xiao Z the probability that he draws two socks of the same color. Of course, Xiao Z wants this probability to be as high as possible, so he may ask multiple queries $(L, R)$ to help him choose.

However, there are cases with $L = R$ in the testdata. Please handle this case specially and output 0/1.

Input Format

The first line contains two positive integers $N$ and $M$. $N$ is the number of socks, and $M$ is the number of queries Xiao Z asks. The next line contains $N$ positive integers $C_i$, where $C_i$ denotes the color of the $i$-th sock; the same color is represented by the same integer. Then follow $M$ lines, each containing two positive integers $L, R$ representing a query.

Output Format

Output $M$ lines. For each query, output a fraction $A/B$ on a single line representing the probability that two randomly chosen socks from the interval $[L, R]$ have the same color. If this probability is $0$, output 0/1. Otherwise, $A/B$ must be in lowest terms (see the sample).

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

2/5
0/1
1/1
4/15

Hint

In $30\%$ of the testdata, $N, M \leq 5000$.

In $60\%$ of the testdata, $N, M \leq 25000$.

In $100\%$ of the testdata, $N, M \leq 50000$, $1 \leq L \leq R \leq N$, $C_i \leq N$.

Translated by ChatGPT 5