Bài tập

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 

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.

Hoành Sơn là một địa điểm du lịch nổi tiếng trên toàn thế giới bởi sự hùng vĩ cũng như sự đa dạng phong phú về các dãy núi và những cây cầu bắc qua. Địa điểm du lịch Hoành Sơn có các dịch vụ tham quan theo yêu cầu. Cụ thể là bạn chỉ việc đưa ra yêu cầu lộ trình, sau đó dịch vụ sẽ tính toán và đưa bạn đi qua các cây cầu và ngọn núi theo đúng yêu cầu về lộ trình.

Địa điểm du lịch ở đây có \(N\) ngọn núi và \(M\) cây cầu, mỗi cây cầu nối hai ngọn núi nào đó với nhau. Giữa hai ngọn núi bất kì có thể có nhiều cây cầu nối hai ngọn núi đó với nhau. Cũng có thể có những ngọn núi có những cây cầu tự nối với chính nó tạo ra hình vòng cung để những khách du lịch có thể đứng xung quanh ngọn núi tham quan và chụp ảnh. Hiểu đơn giản thì mô hình của khu du lịch là một đa đồ thị vô hướng \(N\) đỉnh \(M\) cạnh.

Các ngọn núi được đánh số từ 1 đến \(N\) và ngọn núi thứ \(i\) có độ cao là \(A_i\). Về độ dốc của các cây cầu thì nó được tính theo chênh lệch chiều cao của hai ngọn núi ở hai đầu cây cầu. Nói cách khác, nếu cây cầu nối hai ngọn núi \(x\) và \(y\) thì độ dốc của nó là \(|A_x - A_y|\).

Sau khi đạt giải quốc gia, Tuấn muốn tự thưởng cho mình chuyến du lịch đến Hoành Sơn sau cả năm trời ôn luyện vất vả và chuẩn bị bước vào đại học. Đến Hoành Sơn, Tuấn muốn thiết kế một hành trình "lên đỉnh siêu dốc", xuất phát từ một ngọn núi nào đó, đi đến các ngọn núi khác với điều kiện ngọn núi sau cao hơn ngọn núi trước, không những thế, độ dốc của cây cầu sau cũng phải lớn hơn độ dốc của cây cầu trước đó. Nghĩa là, nếu như Tuấn quyết định chọn một hành trình đi qua các ngọn núi theo thứ tự \(P_1, P_2, \ldots, P_k\) thì hành trình đó sẽ phải thỏa mãn tính chất:

Yêu cầu: Hãy giúp hướng dẫn viên du lịch cho Tuấn hành trình "lên đỉnh siêu dốc" qua nhiều đỉnh núi nhất và trả lời thắc mắc của Tuấn là có bao nhiêu hành trình khác nhau đạt được nhiều đỉnh núi nhất như vậy. Hai hành trình gọi là khác nhau nếu tồn tại một cây cầu hành trình này có mà hành trình kia không hoặc ngược lại.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) \((1 \leq N \leq 3 \times 10^5,\ 1 \leq M \leq 5 \times 10^5)\).
• Dòng thứ hai chứa độ cao của \(N\) ngọn núi là \(N\) số nguyên dương \(A_1, A_2, ..., A_n\) \((1 \leq A_i \leq 10^9)\).
• Dòng thứ \(i\) trong số \(M\) dòng tiếp theo chứa cặp số nguyên dương \((U_i, V_i)\) là chỉ số hai ngọn núi là hai đầu của cây cầu thứ \(i\) \((1 \leq U_i, V_i \leq N)\).

Output

In ra kết quả trên 2 dòng:

• Dòng đầu tiên ghi ra một số nguyên là số lượng đỉnh núi của hành trình tìm được.
• Dòng thứ hai ghi ra một số nguyên là phần dư trong phép chia số lượng lộ trình khác nhau tìm được cho \(10^9 + 7\).

Example

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

3
1

Scoring

• Có 22% số test ứng với \(N \leq 20\).
• Có 28% số test khác ứng với \(N \leq 500\).
• Có 20% số test khác ứng với \(M = N - 1\), và các đỉnh trong đồ thị liên thông với nhau.
• 30% còn lại không có giới hạn gì thêm.