You are given an array \(Arr\) of size N, containing integers. You have to answer Q queries where each query is of the form :

K L R :- If \(K=0\), then you have to find the probability of choosing an even number from the segment \([L,R]\) (both Inclusive) in the array \(Arr\).

K L R :- If \( K=1\), then you have to find the probability of choosing an odd number from the segment \([L,R]\) (both Inclusive) in the array \(Arr\).

For each query print two integers p and q which represent the probability \(p/q\). Both p and q are reduced to the minimal form.

If p is 0 or p is equal to q print \(p/q\) alone.

Constraints:

• \(1 ≤ T ≤ 10\)
• \(1 ≤ N,Q ≤ 10000\)
• \(1 ≤ Arr_i ≤ 1000000\)
• \(0 ≤ K ≤ 1\)
• \(1 ≤ L ≤R≤ N\)

Format of the input file:
First line : T i.e Number of testcases.
For each testcase :
First line : Two space separated integers N and Q.
Second line : N space separated integers denoting the array .
Next Q lines ; Three space separated integers K L and R.

Format of the output file:
Output the answer to each query in a separate line.