イヅア高校の生徒たちは、来年の体育祭に備えて移動マスゲームの練習をしています。このマスゲームでは、先生の号令に合わせて生徒達が移動しながら体の向きを変えます。
移動マスゲームでは、1から$N$までの番号が付いた区画にいる生徒に対して、先生が指示を出します。区画は1から順に西から東に一列に並んでいます。初めそれぞれの生徒はどこかの区画にいて、全員が北を向いて立っています。どの区画も生徒を全員収容できる広さがあります。先生は、指示の時点で何番から何番までの区画にいる生徒が、どれだけ移動するか伝えます。
先生が$a,b,c$と３つの数を叫ぶと、その時点で$a$番目から$b$番目までの区画にいる生徒が全員、$c$の値に応じて一斉に移動して、さらに体の向きを180度変えます。$c$は整数で、正なら生徒が東に、負なら生徒が西に、数の大きさ１ごとに1区画分移動し、移動の前に北向きだった生徒は移動後に南向きになり、南向きだった生徒は北向きになります。このとき、$a$番目よりも小さい番号の区画に移動することを指示された生徒は$a$番目の区画に移動し、$b$番目よりも大きい番号の区画に移動することを指示された生徒は$b$番目の区画に移動します。このため、$a$番目から$b$番目までの区画にいても、まったく移動しない生徒がいることもありますが、そのような生徒も必ず体の向きを180度変えます。
指示を出す先生は、ある時点での生徒たちの向きが、移動マスゲームの美しさに関係があると考えています。そのため、いくつかの時点での指示の直後で、指定した範囲の区画にいる生徒のうち北を向いている生徒の人数から南を向いている生徒の人数を引いた値を知りたいと考えています。
区画の数と生徒の人数、それぞれの生徒が初めにいる区画の番号、先生の号令と人数の差を調べる問い合わせの情報が与えられたとき、各問い合わせについて、指定した範囲の区画にいる生徒のうち、北を向いている生徒の人数から南を向いている生徒の人数を引いた値を求めるプログラムを作成せよ。
入力は以下の形式で与えられる。
$N$ $M$ $x_1$ $x_2$ : $x_M$ $Q$ $info_1$ $info_2$ : $info_Q$
１行目に区画の数$N$ ($2 \leq N \leq 10^9=10$の$9$乗)と生徒の人数$M$ ($1 \leq M \leq 100,000$)が与えられる。続く$M$行に、$i$番目の生徒が最初にいる区画の番号$x_i$ ($1 \leq x_i \leq N$)が与えられる。続く１行に号令と問い合わせに関する情報の数$Q$ ($1 \leq Q \leq 100,000$)が与えられる。続く$Q$行に号令と問い合わせに関する情報$info_i$が与えられる。情報は時系列順に並んでいる。各$info_i$は、以下のいずれかの形式で与えられる。
1 $a$ $b$ $c$
または
2 $d$ $e$
1 $a$ $b$ $c$ は、$a$番目から$b$番目までの区画にいる生徒が数$c$に応じて移動しつつ向いている方向を変えよという号令を表す。ただし、$1 \leq a \leq b \leq N$、$-N < c < N$で$c \ne 0$である。2 $d$ $e$は、その時点で$d$番目から$e$番目までの区画にいる生徒のうち、北を向いている生徒の人数から南を向いている生徒の人数を引いた値がいくつになるかという問い合わせを表す。ただし、$1 \leq d \leq e \leq N$である。問い合わせに関する情報は１つ以上与えられる。
各問い合わせについて、問い合わせで指定した範囲の区画にいる生徒のうち、北を向いている生徒の人数から南を向いている生徒の人数を引いた値を１行に出力する。
6 6 1 1 2 3 5 6 11 2 1 6 1 4 6 -2 2 2 4 2 3 4 1 1 4 1 2 1 1 2 2 2 2 3 3 2 4 4 2 5 5 2 6 6
6 0 -1 0 -2 -1 1 0 0