17728번 - Walls 서브태스크다국어

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

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

レーザーステージは，N 個の防壁が配置された場所が舞台となっている．舞台は長方形であり， 1 × 1 の 正方形のマスに分かれている．各マスは 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 ≦ i ≦ 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 ≦ i ≦ N) には，整数 A_i, B_i が空白を区切りとして書かれている．これは， ステージ開始時において，防壁 i がマス (A_i, i) からマス (B_i, i) までの位置に置かれていることを表す．
• 続く M 行のうちの j 行目 (1 ≦ j ≦ M) には，整数 P_j が書かれている．これは，j 回目の攻撃におい て，敵はマス (P_j, N + 1) からマス (P_j, 0) に向かってレーザーをまっすぐに発射することを表す．

標準出力に N 行出力せよ．i 行目 (1 ≦ i ≦ N) には，防壁 i の移動回数の最小値を出力せよ．

• 1 ≦ N ≦ 200 000．
• 1 ≦ M ≦ 200 000．
• 0 ≦ A_i ≦ B_i ≦ 1 000 000 000 (1 ≦ i ≦ N)．
• 0 ≦ P_j ≦ 1 000 000 000 (1 ≦ j ≦ M)．

• N = 1 を満たす．

• A_i = 0 (1 ≦ i ≦ N) を満たす．

追加の制限はない．