Little Z's Socks

Problem Description

As a scatterbrained person, Little Z spends a long time every morning picking out a pair of socks from a pile of colorful ones. Finally one day, unable to bear this annoying sock-finding process any longer, Little Z decides to leave it to fate…

Specifically, Little Z labels the $N$ socks from $1$ to $N$, and then picks two socks from indices $L$ to $R$. Although Little Z does not care whether the two socks form a complete pair, or even whether they are a left and a right sock, he does care about their color — wearing two socks of different colors would be embarrassing.

Your task is to tell Little Z the probability of drawing two socks of the same color. Of course, Little Z wants this probability to be as high as possible, so he may ask several $(L,R)$ queries to help himself choose.

Input Format

The first line of the input contains two positive integers $N, M$ ($1\leq N, M \leq 50000$). $N$ is the number of socks, and $M$ is the number of queries Little Z makes.

The next line contains $N$ positive integers $C_i$ ($1\leq C_i \leq N$), where $C_i$ is the color of the $i$-th sock; the same color is represented by the same number.

The next $M$ lines each contain two positive integers $L, R$ ($1\leq L < R \leq N$), describing one query.

Output Format

Output $M$ lines. For each query, output the fraction $A/B$ on one line, representing the probability of drawing two socks of the same color from the interval $[L, R]$. If this probability is $0$, output 0/1; otherwise $A/B$ must be an irreducible fraction.

Sample Input

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

Sample Output

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

Sample Explanation

• Query 1: there are ${5 \choose 2} = 10$ possible pairs; drawing two $2$'s has $1$ possibility and drawing two $3$'s has $3$ possibilities, so the probability is $(1+3)/10 = 2/5$.
• Query 2: there are ${3 \choose 2} = 3$ possible pairs; it is impossible to draw two socks of the same color, so the probability is $0/1$.
• Query 3: there are ${3 \choose 2} = 3$ possible pairs, all drawing two $3$'s, so the probability is $1/1$.