あなたは，JOI 社が発売したテレビゲームソフトを手に入れた．なかなか良くできたゲームであり，それなりに楽しみながら毎日プレイしていた．

ある日，ゲーマーの中で「レーザー」と呼称されるステージが出現した．どうやらそのステージは極めて難しく，優れたゲーマーでさえもほんのわずかな確率でしかクリアできない物であるらしい．何度もそのステージに挑戦する中であなたは，とても高速な判断を行うことでクリアできる可能性が有ることに気づき，プログラムを作成して対処出来るのではないかと考えた．

レーザーステージは，$N$ 個の防壁が配置された場所が舞台となっている．舞台は長方形であり，$1\times1$ の正方形のマスに分かれている．各マスは $0$ 以上の整数 $x,y$ によって $(x,y)$ と表される．$(0,0)$ は左下隅のマスであり，$(x,y)$ は $(0,0)$ から右に $x$ マス，上に $y$ マス進んだマスを表す．

ステージが始まると敵が出現し攻撃を行う．$M$ 回の攻撃が順番に行われる．$j$ 回目の攻撃で，敵はマス $(P_j,N+1)$ からマス $(P_j,0)$ に向かってレーザーをまっすぐに発射する．

各防壁は $y$ 座標が同じ連続したいくつかのマスに置かれる．防壁 $i$（$1\le i\le N$）は左右の幅 $B_i-A_i+1$，上下の幅 $1$ の長方形であり，ステージ開始時にはマス $(A_i,i)$ からマス $(B_i,i)$ までを占める．あなたは，敵の最初の攻撃の直前と，敵の攻撃と攻撃の合間に何度でも防壁を左右に動かすことができる．1 回の移動で 1 つの防壁を右に 1 マス動かすか，または左に 1 マス動かすことができる．

レーザーは防壁にぶつかると威力が弱くなる．レーザーをすべての防壁にぶつけるように防壁を動かすことで，レーザーの威力を最小にしたい．

あなたは，このステージにおいて，防壁の移動回数をできるだけ少なくしたい．

課題

ステージ開始時の各防壁の位置と，それぞれの敵の攻撃の位置が与えられる．すべてのレーザーをすべての防壁にぶつけるように防壁を動かすとき，それぞれの防壁の移動回数の最小値を求めよ．

入力

標準入力から以下のデータを読み込め．

• 1 行目には，整数 $N,M$ が空白を区切りとして書かれている．これは，このステージには防壁が $N$ 個あり，敵の攻撃が $M$ 回行われることを表す．
• 続く $N$ 行のうちの $i$ 行目（$1\le i\le N$）には，整数 $A_i,B_i$ が空白を区切りとして書かれている．これは，ステージ開始時において，防壁 $i$ がマス $(A_i,i)$ からマス $(B_i,i)$ までの位置に置かれていることを表す．
• 続く $M$ 行のうちの $j$ 行目（$1\le j\le M$）には，整数 $P_j$ が書かれている．これは，$j$ 回目の攻撃において，敵はマス $(P_j,N+1)$ からマス $(P_j,0)$ に向かってレーザーをまっすぐに発射することを表す．

出力

標準出力に $N$ 行出力せよ．$i$ 行目（$1\le i\le N$）には，防壁 $i$ の移動回数の最小値を出力せよ．

制約

すべての入力データは以下の条件を満たす．

• $1\le N\le200\,000$．
• $1\le M\le200\,000$．
• $0\le A_i\le B_i\le1\,000\,000\,000$（$1\le i\le N$）．
• $0\le P_j\le1\,000\,000\,000$（$1\le j\le M$）．

小課題

小課題 1 [10 点]

• $N=1$ を満たす．

小課題 2 [45 点]

• $A_i=0$（$1\le i\le N$）を満たす．

小課題 3 [45 点]

追加の制限はない．

入出力例

入力 1

4 4
0 3
4 4
2 7
8 11
6
4
3
8

出力 1

5
10
1
7

注記

この入力において，防壁の移動回数を最小にする動かし方の 1 つは以下の通りである：

• 1 回目の攻撃の前に，防壁 1 を右に 3 回動かし，防壁 2 を右に 2 回動かし，防壁 3 は動かさず，防壁 4 を左に 2 回動かす．
• 2 回目の攻撃の前に，防壁 1 は動かさず，防壁 2 を左に 2 回動かし，防壁 3 は動かさず，防壁 4 を左に 2 回動かす．
• 3 回目の攻撃の前に，防壁 1 は動かさず，防壁 2 を左に 1 回動かし，防壁 3 は動かさず，防壁 4 を左に 1 回動かす．
• 4 回目の攻撃の前に，防壁 1 を右に 2 回動かし，防壁 2 を右に 5 回動かし，防壁 3 を右に 1 回動かし，防壁 4 を右に 2 回動かす．

この動かし方において，防壁 1 を 5 回，防壁 2 を 10 回，防壁 3 を 1 回，防壁 4 を 7 回動かすことになる．

入力 2

7 11
12 39
22 23
5 38
6 47
10 43
0 50
18 46
38
19
15
1
12
29
29
0
6
40
6

出力 2

34
178
13
6
18
0
36