你買咗 JOI 公司推出嘅一款電視遊戲。呢款遊戲做得相當唔錯，你每日都玩得幾開心。

有一日，你遇到一個玩家之間叫做「雷射」嘅關卡。呢個關卡似乎極之困難，就算係高手，都只有好低機會過關。你挑戰咗好多次之後，發現只要作出極快嘅判斷，就有機會過關，所以諗住寫個程式嚟應付。

雷射關卡嘅場地入面擺咗 $N$ 道防壁。場地係長方形，劃分成 $1\times1$ 嘅正方形格仔。每個格仔用兩個非負整數 $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)$ 嘅位置。喺敵人第一次攻擊之前，同埋每兩次攻擊之間，你都可以任意多次將防壁向左或者向右移動。每次移動可以將一道防壁向右移一格，或者向左移一格。

雷射撞到防壁時，威力就會減弱。你想移動防壁，令雷射撞到所有防壁，從而將雷射嘅威力降到最低。

喺呢個關卡入面，你想令防壁嘅移動次數盡可能少。

任務

畀定關卡開始時每道防壁嘅位置，同埋敵人每次攻擊嘅位置。當你移動防壁，令每道雷射都撞到所有防壁時，求出每道防壁最少要移動幾多次。

輸入格式

由標準輸入讀取以下資料。

• 第一行有兩個用空格分隔嘅整數 $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 \le 200\,000$。
• $1 \le M \le 200\,000$。
• $0 \le A_i \le B_i \le 1\,000\,000\,000$ ($1 \le i \le N$)。
• $0 \le P_j \le 1\,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 向右移 3 次、防壁 2 向右移 2 次、防壁 3 保持唔郁、防壁 4 向左移 2 次。
• 第二次攻擊之前，防壁 1 保持唔郁、防壁 2 向左移 2 次、防壁 3 保持唔郁、防壁 4 向左移 2 次。
• 第三次攻擊之前，防壁 1 保持唔郁、防壁 2 向左移 1 次、防壁 3 保持唔郁、防壁 4 向左移 1 次。
• 第四次攻擊之前，將防壁 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