Server Time: Sun Sep 24, 2017 1:55 pm
Welcome ( logout
1183 - Computing Fast Average
  PDF (English) Statistics Forum
Time Limit: 2 second(s) Memory Limit: 64 MB

Given an array of integers (0 indexed), you have to perform two types of queries in the array.

1.      1 i j v - change the value of the elements from ith index to jth index to v.

2.      2 i j - find the average value of the integers from ith index to jth index.

You can assume that initially all the values in the array are 0.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case contains two integers: n (1 ≤ n ≤ 105), q (1 ≤ q ≤ 50000), where n denotes the size of the array. Each of the next q lines will contain a query of the form:

1 i j v (0 ≤ i ≤ j < n, 0 ≤ v ≤ 10000)

2 i j (0 ≤ i ≤ j < n)

Output

For each case, print the case number first. Then for each query of the form '2 i j' print the average value of the integers from i to j. If the result is an integer, print it. Otherwise print the result in 'x/y' form, where x denotes the numerator and y denotes the denominator of the result and x and y are relatively prime.

Sample Input

Output for Sample Input

1

10 6

1 0 6 6

2 0 1

1 1 1 2

2 0 5

1 0 3 7

2 0 1

Case 1:

6

16/3

7

Note

Dataset is huge. Use faster i/o methods.


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan