Ta có một lưới hai chiều đủ lớn gồm các ô vuông, trải theo cả chiều ngang và chiều dọc. Chọn một ô làm gốc tọa độ. Ô \((x,y)\) là ô đến được khi đi từ gốc sang phải \(x\) ô và lên trên \(y\) ô. Đi sang trái \(a\) ô tương ứng với đi sang phải \(-a\) ô; đi xuống dưới \(a\) ô tương ứng với đi lên trên \(-a\) ô.

Tại thời điểm \(0\), các ô \((X_1,Y_1),(X_2,Y_2),\ldots,(X_N,Y_N)\) có màu đen, và tất cả các ô còn lại có màu trắng.

Với \(t=0,1,2,\ldots\), màu của các ô tại thời điểm \(t+1\) được xác định từ màu tại thời điểm \(t\) như sau:

• Một ô màu đen tại thời điểm \(t\) chuyển thành màu xám tại thời điểm \(t+1\).
• Một ô màu xám tại thời điểm \(t\) chuyển thành màu trắng tại thời điểm \(t+1\).
• Một ô màu trắng tại thời điểm \(t\) chuyển thành màu đen tại thời điểm \(t+1\) nếu ít nhất một trong bốn ô kề cạnh với nó có màu đen tại thời điểm \(t\). Nếu không, ô đó vẫn có màu trắng.

Có \(Q\) truy vấn. Với truy vấn thứ \(j\) (\(1 \le j \le Q\)), hãy tìm số ô màu đen tại thời điểm \(T_j\).

Hãy viết chương trình trả lời các truy vấn khi biết màu của các ô tại thời điểm \(0\) và thông tin truy vấn.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N Q
X_1 Y_1
X_2 Y_2
...
X_N Y_N
T_1
T_2
...
T_Q

Dữ liệu ra

Ghi \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) chứa số ô màu đen tại thời điểm \(T_j\).

Ràng buộc

• \(1 \le N \le 100000\).
• \(1 \le Q \le 500000\).
• \(|X_i| \le 10^9\) (\(1 \le i \le N\)).
• \(|Y_i| \le 10^9\) (\(1 \le i \le N\)).
• \((X_i,Y_i) \ne (X_j,Y_j)\) (\(1 \le i < j \le N\)).
• \(0 \le T_j \le 10^9\) (\(1 \le j \le Q\)).
• \(T_j < T_{j+1}\) (\(1 \le j \le Q-1\)).
• Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

1. \(4\) điểm: \(\lvert X_i\rvert \le 50\), \(\lvert Y_i\rvert \le 50\) với mọi \(1 \le i \le N\); \(T_j \le 50\) với mọi \(1 \le j \le Q\).
2. \(12\) điểm: \(\lvert X_i\rvert \le 1000\), \(\lvert Y_i\rvert \le 1000\) với mọi \(1 \le i \le N\); \(T_j \le 1000\) với mọi \(1 \le j \le Q\).
3. \(8\) điểm: \(X_i=Y_i\) với mọi \(1 \le i \le N\); \(Q=1\).
4. \(8\) điểm: \(X_i=Y_i\) với mọi \(1 \le i \le N\).
5. \(17\) điểm: \(N \le 2000\); \(Q=1\).
6. \(25\) điểm: \(N \le 2000\).
7. \(26\) điểm: Không có ràng buộc bổ sung.

Ví dụ

2 3
0 2
1 0
0
1
2

2
8
12

3 5
0 0
2 2
5 5
0
1
2
3
4

3
12
21
24
26

4 10
-3 -3
3 3
-4 4
4 -4
0
1
2
3
4
5
6
7
8
9

4
16
32
48
56
56
55
56
60
64

Nguồn

JOI Open Contest 2023 - Cell Automaton. Tác giả: Akihito Yoneyama. Đơn vị công bố: JCIOI (Ủy ban Nhật Bản về Olympic Tin học Quốc tế). Giấy phép: CC BY-SA 4.0.