問題文

二次元座標平面上に相異なる N 個の点 P_1, P_2, \ldots, P_N があり、点 P_i の座標は (x_i, y_i) です。

以下の Q 個のクエリを順に処理してください。

• i (1 \leq i \leq Q) 番目のクエリでは、整数 q_i が与えられるので、点 P_{q_i} と N 個の点の間のマンハッタン距離の最大値を出力する。
• つまり、点 P_s と点 P_t のマンハッタン距離を \rm{dist}(P_s, P_t) とするとき、\rm{max}(\rm{dist}(P_{q_i}, P_1), \cdots, \rm{dist}(P_{q_i}, P_N)) の値を出力する。

制約

• 2 \leq N \leq 100000
• 1 \leq Q \leq N
• -10^9 \leq x_i, y_i \leq 10^9
• (x_i, y_i) \neq (x_j, y_j) (1 \leq i < j \leq N)
• 1 \leq q_i \leq N (1 \leq i \leq Q)
• q_i \neq q_j (1 \leq i < j \leq Q)
• 与えられる入力は全て整数

入力例 1

3 3
-1 2
1 1
-2 -3
1
2
3

出力例 1

6
7
7

1 番目のクエリでは点 1 に注目します。

• 点 1 と点 1 のマンハッタン距離は |-1 - (-1)| + |2 - 2| = 0
• 点 1 と点 2 のマンハッタン距離は |-1 - 1| + |2 - 1| = 3
• 点 1 と点 3 のマンハッタン距離は |-1 - (-2)| + |2 - (-3)| = 6

したがって、1 番目のクエリではこれらのマンハッタン距離の最大値である 6 を出力します。

入力例 2

5 3
-2 -2
-1 -1
0 0
1 1
2 2
5
3
1

出力例 2

8
4
8

入力例 3

2 1
-1000000000 -1000000000
1000000000 1000000000
1

出力例 3

4000000000

オーバーフローに注意してください。