你取得了一款由 JOI 公司發售的電視遊戲軟體。這款遊戲製作得相當不錯，你每天都玩得頗為開心。

有一天，出現了一個被玩家稱為「雷射」的關卡。這個關卡似乎極為困難，即使是優秀的玩家，也只有極低的機率能過關。在多次挑戰這個關卡的過程中，你發現只要做出非常快速的判斷，就有可能過關，因此想到也許可以撰寫程式來應對。

雷射關卡的舞台是放置了 $N$ 面防壁的場所。舞台為長方形，分成 $1\times 1$ 的正方形格子。每個格子以非負整數 $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