Bạn đã mua một trò chơi điện tử do công ty JOI phát hành. Đây là một trò chơi khá hay, và bạn vẫn chơi mỗi ngày một cách vui vẻ.

Một ngày nọ, xuất hiện một màn chơi được các game thủ gọi là “Laser”. Có vẻ màn chơi này cực kỳ khó, đến nỗi ngay cả những game thủ giỏi cũng chỉ có xác suất rất nhỏ vượt qua được. Sau nhiều lần thử sức, bạn nhận ra rằng có thể vượt qua nếu đưa ra quyết định cực nhanh, và nghĩ rằng mình có thể viết chương trình để xử lý.

Màn Laser diễn ra tại một khu vực có $N$ bức tường phòng thủ. Khu vực là một hình chữ nhật được chia thành các ô vuông $1\times1$. Mỗi ô được biểu diễn bằng $(x,y)$ với các số nguyên không âm $x,y$. Ô $(0,0)$ là ô ở góc dưới bên trái; ô $(x,y)$ là ô nằm cách đó $x$ ô sang phải và $y$ ô lên trên.

Khi màn chơi bắt đầu, kẻ địch xuất hiện và tấn công. Có $M$ đợt tấn công lần lượt diễn ra. Trong đợt tấn công thứ $j$, kẻ địch bắn một tia laser thẳng từ ô $(P_j,N+1)$ về phía ô $(P_j,0)$.

Mỗi bức tường nằm trên một số ô liên tiếp có cùng tọa độ $y$. Bức tường $i$ ($1\le i\le N$) là hình chữ nhật có chiều ngang $B_i-A_i+1$ và chiều cao $1$; lúc bắt đầu màn chơi, nó chiếm các ô từ $(A_i,i)$ đến $(B_i,i)$. Bạn có thể di chuyển các bức tường sang trái hoặc phải bao nhiêu lần tùy ý ngay trước đợt tấn công đầu tiên và giữa các đợt tấn công. Mỗi lần di chuyển, bạn có thể dịch một bức tường sang phải $1$ ô hoặc sang trái $1$ ô.

Khi va vào một bức tường, sức mạnh của tia laser giảm đi. Bạn muốn giảm sức mạnh của laser xuống mức thấp nhất bằng cách di chuyển các bức tường sao cho tia laser va vào tất cả các bức tường.

Trong màn chơi này, bạn muốn số lần di chuyển các bức tường ít nhất có thể.

Yêu cầu

Cho vị trí ban đầu của từng bức tường và vị trí của mỗi đợt tấn công. Hãy tìm số lần di chuyển tối thiểu của từng bức tường sao cho mọi tia laser đều va vào tất cả các bức tường.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Dòng đầu chứa các số nguyên $N,M$, cách nhau bởi dấu cách. Chúng cho biết màn chơi có $N$ bức tường và kẻ địch tấn công $M$ lần.
• Dòng thứ $i$ ($1\le i\le N$) trong $N$ dòng tiếp theo chứa các số nguyên $A_i,B_i$, cách nhau bởi dấu cách. Chúng cho biết lúc bắt đầu màn chơi, bức tường $i$ chiếm các ô từ $(A_i,i)$ đến $(B_i,i)$.
• Dòng thứ $j$ ($1\le j\le M$) trong $M$ dòng tiếp theo chứa số nguyên $P_j$. Nó cho biết trong đợt tấn công thứ $j$, kẻ địch bắn laser thẳng từ ô $(P_j,N+1)$ về phía ô $(P_j,0)$.

Dữ liệu ra

In $N$ dòng ra đầu ra chuẩn. Dòng thứ $i$ ($1\le i\le N$) chứa số lần di chuyển tối thiểu của bức tường $i$.

Giới hạn

Mọi dữ liệu vào đều thỏa mãn các điều kiện sau.

• $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$).

Nhiệm vụ con

Nhiệm vụ con 1 [10 điểm]

• $N=1$.

Nhiệm vụ con 2 [45 điểm]

• $A_i=0$ ($1\le i\le N$).

Nhiệm vụ con 3 [45 điểm]

Không có giới hạn bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

5
10
1
7

Ghi chú

Với dữ liệu này, một cách di chuyển tối ưu các bức tường như sau:

• Trước đợt tấn công thứ 1, di chuyển tường $1$ sang phải $3$ lần, tường $2$ sang phải $2$ lần, không di chuyển tường $3$, và di chuyển tường $4$ sang trái $2$ lần.
• Trước đợt tấn công thứ 2, không di chuyển tường $1$, di chuyển tường $2$ sang trái $2$ lần, không di chuyển tường $3$, và di chuyển tường $4$ sang trái $2$ lần.
• Trước đợt tấn công thứ 3, không di chuyển tường $1$, di chuyển tường $2$ sang trái $1$ lần, không di chuyển tường $3$, và di chuyển tường $4$ sang trái $1$ lần.
• Trước đợt tấn công thứ 4, di chuyển tường $1$ sang phải $2$ lần, tường $2$ sang phải $5$ lần, tường $3$ sang phải $1$ lần, và tường $4$ sang phải $2$ lần.

Theo cách này, tường $1$ được di chuyển $5$ lần, tường $2$ được di chuyển $10$ lần, tường $3$ được di chuyển $1$ lần, và tường $4$ được di chuyển $7$ lần.

Lúc bắt đầu màn chơi; đợt tấn công thứ 1; đợt tấn công thứ 2; đợt tấn công thứ 3; đợt tấn công thứ 4.

Dữ liệu vào 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

Dữ liệu ra 2

34
178
13
6
18
0
36