Bài tập

Một khu dân cư rộng lớn được chia thành một bảng \(n \times m\), trong đó ô \((i, j)\) biểu thị một ngôi nhà ở tọa độ hàng \(i\) và cột \(j\). Mỗi ngôi nhà đều có mức tiêu thụ điện năng tối thiểu là \(a_{i,j}\) (tính bằng watt), và cần một trạm điện gần đó để cung cấp đủ công suất.

Một kỹ sư điện lực được giao nhiệm vụ lắp đặt các trạm điện trong khu dân cư này. Mỗi trạm được đặt tại một ô \((i, j)\) sẽ có phạm vi bao phủ là một hình chữ nhật có góc trên bên trái là \((i, j)\) và góc dưới bên phải là \((i + r - 1, j + s - 1)\), miễn sao toàn bộ hình chữ nhật vẫn nằm trong khu dân cư.

Để đảm bảo tất cả các hộ trong khu vực được bao phủ đều được cấp điện, trạm đặt tại \((i, j)\) cần có công suất ít nhất bằng giá trị lớn nhất trong hình chữ nhật nói trên. Kỹ sư cần xác định cho mỗi vị trí \((i, j)\) công suất tối thiểu cần có nếu đặt trạm điện tại đó.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \le n, m \le 3000)\) --- số hàng và cột của khu dân cư.

Mỗi dòng trong \(n\) dòng tiếp theo chứa \(m\) số nguyên \(a_{i,j}\) \((0 \le a_{i,j} \le 10^4)\) --- mức tiêu thụ điện năng tối thiểu tại từng hộ dân.

Dòng cuối cùng chứa hai số nguyên \(r\) và \(s\) \((1 \le r \le n, 1 \le s \le m)\) --- kích thước chiều cao và chiều rộng của khu vực mà mỗi trạm điện có thể bao phủ.

Output

Để giảm tải kích thước đầu ra, bạn sẽ chỉ in ra \(n-r+1\) số nguyên.

Số nguyên thứ \(i\) được tính theo công thức sau:

• \(\quad\) Gọi \(E[j]\) là công suất tối thiểu cần được đặt tại ô \((i, j)\) với (\(1 \le j \le m-s+1\)).

• \(\quad\) Khi đó cần in ra \(E[1] + E[2] + \cdots + E[m-s+1]\).

Example

3 3
1 1 2
2 3 4
4 3 2
2 1

9
11

Scoring

• Subtask 1 (15 điểm): \(n, m \le 40\)
• Subtask 2 (25 điểm): \(n, m \le 300\)
• Subtask 3 (20 điểm): \(n, m \le 1000\)
• Subtask 4 (40 điểm): Không có ràng buộc bổ sung

Thành phố X là một thành phố rộng lớn được chia làm \(n\) phân khu. Các phân khu được nối với nhau bởi \(n - 1\) con đường hai chiều, mỗi con đường nối trực tiếp giữa hai phân khu nào đấy sao cho đảm bảo luôn tồn tại đường đi giữa hai phân khu bất kỳ.

Là thành phố lớn nhất nhì trong cả nước, mật độ phương tiện giao thông ở đây là vô cùng khổng lồ, dẫn đến gánh nặng rất lớn về chi phí bảo trì và sửa chữa và bảo trì cơ sở hạ tầng. Do đó, chính quyền thành phố đã cho xây dựng ở mỗi phân khu một trạm kiểm soát.

Khi một phương tiện giao thông di chuyển tới một phân khu, phương tiện bắt buộc phải đi qua trạm kiểm soát này. Mỗi trạm kiểm soát sẽ có một mức giới hạn tải trọng, trạm kiểm soát ở phân khu \(i\) sẽ có mức giới hạn là \(l_{i}\) kg. Giả sử một phương tiện đi qua và có tải trọng lớn hơn giới hạn tải trọng của trạm kiểm soát, chủ phương tiện phải trả cho trạm kiểm soát đó khoảng phạt là \(1\) đồng cho mỗi kg vượt giới hạn. Cụ thể hơn, nếu một phương tiện có tải trọng \(w\) đi qua trạm kiểm soát ở phân khu \(i\), chủ phương tiện đó phải trả cho trạm kiểm soát đó \(\max(w - l_{i}, 0)\) đồng.

Bạn biết được ngày hôm nay đã có \(m\) phương tiện di chuyển, phương tiện \(i\) di chuyển từ phân khu \(s_{i}\) tới phân khu \(t_{i}\) với trọng tải \(w_{i}\) (Lưu ý rằng phương tiện cũng phải đi qua trạm kiểm soát của điểm xuất phát và đích đến). Với mỗi trạm kiểm soát, hãy cho biết sau ngày hôm nay trạm kiểm soát đó đã thu được bao nhiêu tiền.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((1 \leq n, m \leq 3 \times 10^{5})\).

• Trong \(n - 1\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(u_{i}\) và \(v_{i}\) \((1 \leq u_{i}, v_{i} \leq n)\) có nghĩa là có đường nối trực tiếp giữa phân khu \(u_{i}\) và \(v_{i}\).

• Dòng tiếp theo chứa \(n\) số nguyên \(l_{i}\) \((0 \leq l_{i} \leq 10^{9})\).

• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(s_{i}, t_{i}\) và \(w_{i}\) \((1 \leq s_{i}, t_{i} \leq n, 1 \leq w_{i} \leq 10^{9})\).

Output

• Một dòng duy nhất chứa \(n\) số nguyên, số thứ \(i\) là số tiền mà trạm kiểm soát ở phân khu \(i\) thu được sau ngày hôm nay.

Example

4 1
1 2
2 3
3 4
1 2 3 4
1 4 3

2 1 0 0 

8 3
1 2
2 3
2 4
3 5
4 6
3 7
3 8
2 2 2 2 2 2 2 2
3 6 7
7 8 4
5 1 1

0 5 7 5 0 5 2 2 

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n, m \leq 100\).

• Subtask \(2\) (\(25\%\) số điểm): Thành phố có dạng đường thẳng.

• Subtask \(3\) (\(25\%\) số điểm): \(l_{i} = 0\) với mọi \(1 \leq i \leq n\).

• Subtask \(4\) (\(25\%\) số điểm): Không có ràng buộc gì thêm.

Một hầm ngục mới vừa xuất hiện. Hầm ngục có dạng ma trận vuông gồm \(n\) × \(n\) phòng chứa rất nhiều quái vật. Phòng ở hàng \(i\) và cột \(j\) được gọi là phòng \((i, j)\). Khi tiến vào hầm ngục, người chơi sẽ được dịch chuyển đến một phòng ngẫu nhiên. Người chơi phải tiêu diệt hết quái vật mới có thể di chuyển đến các phòng kề cạnh. Sau khi quét sạch được một phòng, người chơi sẽ nhận được một rương phần thưởng có giá trị \(a_{i, j}\). Trong hầm sẽ có một phòng dịch chuyển, sau khi dọn sạch phòng đó, người chơi sẽ nhận được rương ở phòng đó và cổng dịch chuyển sẽ xuất hiện để thoát khỏi hầm ngục.

Để hạn chế tổn thất, hệ thống đặt ra một lời nguyền đó là sau khi thoát khỏi hầm ngục, người chơi chỉ có thể giữ lại một rương có giá trị phần thưởng nhỏ nhất trong tất cả các rương nhận được.

Jung, một người chơi giàu kinh nghiệm, đã nhanh chóng tìm được bản đồ chi tiết giá trị phần thưởng ở các phòng và cách xác định hai phòng xuất phát và dịch chuyển khi vào hầm ngục. Vì đang bận rộn với đống công việc của công hội nên anh đã liệt kê ra danh sách các khả năng và nhờ bạn lên kế hoạch tấn công.

Yêu cầu: Cho \(q\) truy vấn có dạng \(x\) \(y\) \(u\) \(v\) \((1 ≤ x, y, u, v ≤ n)\), hãy tính toán nếu xuất phát ở phòng \((x, y)\) và phòng dịch chuyển là phòng \((u, v)\) thì khi ra khỏi hầm ngục, giá trị phần thưởng được giữ lại lớn nhất là bao nhiêu.

Input

Dòng đầu tiên chứa hai số nguyên \(n\), \(q\) \((1 ≤ n ≤ 500; 1 ≤ q ≤ 4·10^5)\).

\(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên \(a_{i, j}\) \((1 ≤ a_{i, j} ≤ 10^5)\).

\(q\) dòng cuối dùng, mỗi dòng chứa bốn số nguyên \(x, y, u, v\) \((1 ≤ x, y, u, v ≤ n)\). Dữ liệu đảm bảo \((x + u)^2 + (y + v)^2 > 4xu + 4yv\).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

In ra \(q\) dòng, mỗi dòng in ra giá trị phần thưởng lớn nhất tương ứng với từng khả năng trong dữ liệu vào.

Example

5 3
8 4 1 2 4
2 3 5 6 5
1 2 1 5 2
9 5 8 4 7
4 5 1 3 9
1 1 4 1
1 4 3 2
5 3 2 5

3
2
1

Scoring

(\(10\) điểm) \(n ≤ 100\) và \(q ≤ 100\)

(\(20\) điểm) \(n ≤ 100\) và \(q ≤ 2000\)

(\(50\) điểm) \(n ≤ 300\) và \(q ≤ 10^5\)

(\(20\) điểm) \(n ≤ 500\) và \(q ≤ 4·10^5\)

Bạn được cho một mảng gồm \(n\) phần tử chưa được tô màu. Ban đầu, mỗi phần tử có giá trị bằng \(0\).

Bạn cần xử lý \(q\) truy vấn dạng \((l, r, c)\) --- tô toàn bộ các phần tử từ chỉ số \(l\) đến \(r\) bằng màu \(c\). Mỗi truy vấn sẽ ghi đè lên các giá trị đã tô trước đó. Sau tất cả các truy vấn, hãy in ra màu cuối cùng của từng phần tử.

\InputFile

• Dòng đầu gồm hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^6\)) --- độ dài mảng và số truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(l, r, c\) --- truy vấn tô màu đoạn \([l, r]\) bằng màu \(c\)(\(1 \le l \le r \le n\), \(c \le 10^9\)).

\OutputFile
In ra trên 1 dòng \(n\) số nguyên, số thứ \(i\) chứa màu cuối cùng của phần tử ở vị trí \(i\).

\Scoring

• Có \(30\%\) số điểm ứng với \(n, q \le 1000\).
• Có \(30\%\) số điểm ứng với \(n, q \le 10^5\).
• \(40\%\) số điểm còn lại không có ràng buộc thêm.

Example

4 3
1 3 2
2 4 6
2 3 7

2 7 7 6