Bạn vừa mua một trò chơi điện tử do công ty JOI phát hành. Một ngày nọ, màn chơi được gọi là "Laser" xuất hiện. Màn này cực kỳ khó, ngay cả người chơi giỏi cũng chỉ có xác suất rất nhỏ vượt qua. Sau nhiều lần thử, bạn nhận ra rằng có thể thắng nếu đưa ra quyết định đủ nhanh và nghĩ đến việc viết chương trình hỗ trợ.

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

Khi màn chơi bắt đầu, kẻ địch thực hiện lần lượt \(M\) đợt tấn công. Trong đợt thứ \(j\), kẻ địch bắn một tia laser thẳng từ ô \((P_j,N+1)\) đến ô \((P_j,0)\).

Mỗi bức tường chiếm một số ô liên tiếp có cùng tọa độ \(y\). Tường \(i\) có chiều ngang \(B_i-A_i+1\), chiều dọc \(1\) và ban đầu chiếm các ô từ \((A_i,i)\) đến \((B_i,i)\). Ngay trước đợt tấn công đầu tiên và giữa hai đợt tấn công liên tiếp, 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 ý. Mỗi lần di chuyển, bạn chọn một bức tường và dịch nó đúng một ô sang trái hoặc sang phải.

Laser yếu đi khi va vào tường. Bạn muốn di chuyển các tường sao cho mọi tia laser đều va vào tất cả \(N\) bức tường, đồng thời giảm số lần di chuyển.

Yêu cầu

Với từng bức tường, hãy tìm số lần di chuyển nhỏ nhất của riêng bức tường đó để mọi tia laser đều va vào nó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N,M\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\), mô tả vị trí ban đầu của tường \(i\).
• \(M\) dòng tiếp theo, dòng thứ \(j\) chứa số nguyên \(P_j\), mô tả vị trí tia laser của đợt tấn công thứ \(j\).

Dữ liệu ra

In ra \(N\) dòng. Dòng thứ \(i\) chứa số lần di chuyển nhỏ nhất của tường \(i\).

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le M \le 200\,000\).
• \(0 \le A_i \le B_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
• \(0 \le P_j \le 1\,000\,000\,000\) với mọi \(1 \le j \le M\).

Phân nhóm

• Nhóm 1 (10 điểm): \(N=1\)
• Nhóm 2 (45 điểm): \(A_i=0\) với mọi \(1 \le i \le N\)
• Nhóm 3 (45 điểm): Không có ràng buộc bổ sung

Ví dụ

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

5
10
1
7

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

34
178
13
6
18
0
36