You are given an array of $N$ positive integers $(A_1,A_2,A_3,$dots,$A_N)$ and an integer $K.$ You are required to support $Q$ queries of the following types:

$1LRx$ : Your task is to add the value $x$ to all the array elements in subarray $L,R.$

$2LR$ : Your task is to print the minimum number of array elements that must be removed from subarray $L,R$ so that all the remaining elements in the subarray have the same remainder when divided by $K.$

A subarray is an array composed of a contiguous block of the original array elements. For example, all the subarrays of the array $1,2,3$ are $[],[1],[2],[3],[1,2],[2,3],$ and $1,2,3.$

Note

You are allowed to remove no elements.

The array remains the same after solving the second query, that is$,$ the array elements are not removed after each operation that is given in the second query.

There is at least one query of the second type.

Input format

The first line contains three space$-$separated integers $N,K,$ and $Q.$

The second line contains $N$ space$-$separated integers $A_i$ denoting the array elements.

Each of the next $Q$ lines contains one of the defined queries.

Output format

For each query of the second type, print a single integer denoting the answer for that query.

Constraints