A I Hate Lazy Segment Tree

harurun君は区間代入区間和取得問題が正解できないのでLazy Segment Treeが嫌いになってしまいました。

あなたはある部屋の管理人です。 部屋には、横一列に並んだ $N$ 個の宝箱、宝箱 $1$、宝箱 $2$、...、宝箱 $N$ があります。 最初、それぞれの宝箱には $0$ 枚以上のコインが入っていますが、あなたは中身の数を知りません。 宝箱の中のコインの枚数は、取引相手の商人の行動によって変化します。

最初に宝箱 $i$ に入っていたコインの枚数を $\Gamma_i$ とし、現在の宝箱 $i$ に入っているコインの枚数を $A_i$ とします。 最初、$A_i=\Gamma_i$ です。

あなたのタスクは、気まぐれな商人から出される $Q$ 個の要求に、魔法を使うことで、順番にすべて正しく答えることです。

<魔法>

• 範囲 $[\alpha,\beta]$ を指定すると、宝箱 $\alpha$、宝箱 $\alpha+1$、...、宝箱 $\beta$ に最初に入っていたコインの枚数の総和 $\sum_{i=\alpha}^{\beta}\Gamma_i$ を知ることができる。
• この魔法は、$1$ つのテストケースにつき合計で $3Q-1$ 回まで使うことができる。

<商人の要求>

• 商人の要求は $5$ つの整数 $(L,R,X,V,W)$ で表され、以下の順に処理を行う。
  1. 商人が、宝箱 $L$、宝箱 $L+1$、...、宝箱 $R$ のすべての宝箱の中身を捨て、それぞれ $X$ 枚のコインを入れ直す。つまり、$i=L,L+1,\ldots,R$ について、$A_i\gets X$ と更新される。
  2. あなたが、宝箱 $V$、宝箱 $V+1$、...、宝箱 $W$ に現在入っているコインの枚数の総和 $\sum_{i=V}^{W}A_i$ を計算し、商人に答える。ただし、答えるために必要な場合、この手順2の直前にのみ、上記の魔法を (テストケースごとの合計制限回数が許す限り) 何度でも使用することができる。

$T$ 個のテストケースが与えられるので、それぞれについて解いてください。

最初に、テストケース数を表す $T$ が与えられます。

$T$

テストケースの最初に、 $N$ と $Q$ が与えられます。

$N$ $Q$

各商人の要求では最初に、 $L, R, X, V, W$ が与えられます。

$L$ $R$ $X$ $V$ $W$

あなたは入力を受け取ったあとに、魔法の使用または商人への解答をすることができます。 出力をした後は必ず flush をしてください。

魔法を使用する場合は、魔法の制約を満たす整数 $\alpha, \beta$ を以下のように出力してください。

? $\alpha$ $\beta$

これに対して、 $U=\sum_{i=\alpha}^{\beta}\Gamma_i$ としてジャッジから以下のように与えられます。

$U$

この後、もう一度魔法の使用または商人への解答をすることができます。 テストケースごとの合計制限回数を越さなければ、各要求で好きな回数魔法を使用することができます。

解答をする場合は、 $ans=\sum_{i=V}^{W}A_{i}$ として以下のように出力してください、

! $ans$

これに対してジャッジからの返答はありません。 次の要求がある場合はその要求を処理してください。 すべての要求が終了した場合は次のテストケースに移ってください。 すべてのテストケースが終了した場合は、ただちにプログラムを終了してください。