Suddenly, A Tempest 2

問題文

平面上に$N$個の点$1,2,\dots,N$があり、点$i$の座標は$(X_i,Y_i)$です。 次の $M$ 個の操作を行った後、 $Q$ 個のクエリに答えてください。

$M$ 個の各操作では、 $2$ つの整数 $x_j, a_j$ $(1 \le j \le M)$ が与えられます。 次に、以下の操作を行ってください。

• $N$ 個の点 $(X_i, Y_i)$ $(1 \le i \le N)$ に対して、$X_i < x_j$ ならば、 $Y_i$ を $Y_i-a_j$ に置き換え、$X_i \ge x_j$ ならば、 $Y_i$ を $Y_i+a_j$ に置き換える。

$Q$ 個の各クエリでは、$2$ つの整数 $s_k,t_k$ $(1 \le k \le Q)$が与えられます。 点 $s_k$ と 点$t_k$ のマンハッタン距離を求めてください。

ここで、点 $(X_a,Y_a)$ と 点$(X_b,Y_b)$ のマンハッタン距離とは、$|X_a-X_b|+|Y_a-Y_b|$ と定義される値です。

制約

• $1 \le N \le 10^5$
• $1 \le M \le 10^5$
• $1 \le Q \le 10^5$
• $-1 \times 10^9 \le X_i, Y_i \le 10^9$
• $-1 \times 10^9 \le x_j \le 10^9$
• $-1 \times 10^9 \le a_j \le 10^9$
• $1 \le s,t \le N$

入力

出力

各クエリへの $Q$ 行で解答してください

サンプル

入力例1

4
4 2
1 3
5 1
-1 -1
2
2 1
5 -2
3
1 2
2 3
3 4

出力例1

4
8
6

初期状態では以下のような配置です

1回目の操作では、

• 直線 $x=2$ より右側の部分(境界含む)は $y$ 座標が $+1$ だけ移動
• 直線 $x=2$ より左側の部分(境界含まない)は $y$ 座標が $-1$ だけ移動

2回目の操作では、

• 直線 $x=5$ より右側の部分(境界含む)は $y$ 座標が $-2$ だけ移動
• 直線 $x=5$ より左側の部分(境界含まない)は $y$ 座標が $+2$ だけ移動

します。よって、順に

• 点$1$：$(4,2) \rightarrow (4,5)$
• 点$2$：$(1,3) \rightarrow (1,4)$
• 点$3$：$(5,1) \rightarrow (5,0)$
• 点$4$：$(-1,-1) \rightarrow (-1,0)$

に移動します。このとき、

• クエリ1：点1と点2のマンハッタン距離は、$|4-1|+|5-4|=4$
• クエリ2：点2と点3のマンハッタン距離は、$|1-5|+|4-0|=8$
• クエリ3：点3と点4のマンハッタン距離は、$|5-(-1)|+|0-0|=6$

になります。