Problem Description

You have a sequence $A$ of length $n$ and a positive integer $k$. Initially, all elements in $A$ are set to $0$.
Now there are $q$ operations, these operations can be divided into two types.
$1$ $l$ $r$ $x$ $: \forall i \in [l,r] A_i = A_i + x$
$2$ $l$ $r$ $:$ Find $\min\limits_{i=l}^{r-k+1} ( \max\limits_{j=i}^{i+k-1} A_j )$ $(r-l+1 \geq k)$

Input

The first line contains an integer $T (T \leq 5)$, denoting the number of test cases.
Each test case contains $q + 2$ lines
The first line contains three integer $n, k(2 \leq k \le n \leq 5 \times 10^8)$ and $q(1 \leq q \leq 10^5)$.
The next $q$ lines describe operations of two types:
$1$ $l$ $r$ $x$ $: \forall i \in [l,r] A_i = A_i + x$ $(|x| \leq 10^4)$
$2$ $l$ $r$ $:$ Find $\min\limits_{i=l}^{r-k+1} ( \max\limits_{j=i}^{i+k-1} A_j )$ $(r-l+1 \geq k)$
It is guaranteed that the sum of $q$ won't exceed $2 \times 10^5$.

Output

For each operation of type $2$, output the answer in a single line.

2
5 3 3
1 2 5 2
1 3 4 -1
2 1 4
10 4 10
1 1 6 6
1 3 8 -6
2 2 6
1 4 8 -8
1 4 9 4
1 4 5 -7
2 4 8
1 6 7 8
1 1 3 -2
2 3 7

2
0
-4
4