# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Yet Another Update Query Problem

Given an array of **n** elements, you have to do **Q** operations. The operations can be of the following two types.

**Operation 1: Update(L,R,v): You should add v to all A _{i} where L<=i<=R**

**Operation 2: Query(L,R,v): You should output the frequency of the number v in the range from Lth to Rth index in the array.**

The value of any element of the array will not be more than 200000 or less than 0 after any operation.

#### Input

In the first line, an integer **T** denoting the number of test cases will be given. Each test case will contain the number **n** and **q** in the first line, the number of elements in the array and the total number of queries.The next line will contain **n** integers denoting the elements of the initial array. Then **q** lines will follow.

Each of the lines will contain 4 integers, **type, L, R, v**. If type = 1, then this would mean an operation of the first type i.e **an update operation.** Otherwise it would mean an operation of the second type i.e **a query operation**.

**Constraints:**

**1 <= T <= 5**

**1 <= n <= 100000**

**1 <= q <= 100000**

**1 <= L <= R <= n**

**-100000 <= v <= 100000**

**1 <= type <= 2**

**The initial array will contain non negative numbers less than or equal to 100000.**

The value of any element of the array will not be more than 100000 or less than 0 after any operation.

#### Output

For each test case, print the case number in one line. Then print the result for each query of type 2 in different lines. Refer to the sample section for input format.

#### Samples

Input | Output |
---|---|

1 5 5 1 2 3 4 5 2 3 4 3 1 3 4 -2 2 3 4 3 1 4 4 -1 2 3 4 1 | Case 1: 1 0 2 |

Login to submit