問題

長さ$N$の数列$x=(x_0,x_1,x_2,\dots ,x_{N-1})$がある。 始めは数列$x=(0,0,0,\dots ,0)$とする。 以下の$2$種類のクエリが$Q$個与えられるので順番に処理せよ。

• 区間加算クエリ ! L R K
  $L\le i<R$について、$x_i$を$x_i+K$に更新する。
• 質問クエリ?
  数列$x$が現在と同一の値を最初にとるのは何番目のクエリの後であるか答える。 初期状態は$0$番目のクエリの後であるとする。
  つまり、答えようとしている質問クエリを$q$番目のクエリ($1\le q\le Q$)とし、$i$番目のクエリの処理後の$x$の値を$x^i$と書く(初期状態のため$x^0=(0,0,0,\dots ,0)$とする)としたとき、$min\{i\mid 0\le i\le Q\wedge x^i=x^{q-1}\}$を出力する。

入力

N Q
$C_1$ ...
$C_2$ ...
...
$C_Q$ ...

$1$行目には、数列の長さを表わす整数$N$ ($1\le N\le {10}^6$)とクエリの数を表す整数$Q$ ($1\le Q\le {10}^5$)が与えられる。 $i+1$行目($1\le i\le Q$)には、問題文中のクエリのいずれかの形式で与えられる。 ただし区間加算クエリであるとき、区間の左端$L_i$は$0\le L_i<N$、区間の右端$R_i$は$L_i<R_i\le N$、加算する量$K_i$は $-100<K_i\le 100$を満たし、いずれも整数とする。

出力

質問クエリに対して、与えられた順番に答えを出力してください。 出力毎に改行してください。

サンプル

3 6
! 1 3 1
! 0 2 2
! 0 3 -2
?
! 2 3 2
?

3
1

3 2
?
?

0
0

100000 6
! 0 100000 1
! 0 100000 2
! 0 100000 3
! 0 100000 4
! 0 100000 -7
?

2