Bài tập

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 

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\)

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.

3M là một học sinh chuyên Văn nhưng cô ấy rất ham mê tìm hiểu các cấu trúc dữ liệu.
Hôm nay cô ấy được thầy Nhật dạy về cấu trúc dữ liệu deque, thứ có thể giúp bạn
thêm bớt ở cả hai đầu của một dãy số. Sau khi học xong, 3M đã nghĩ ra một bài toán
truy vấn rất hấp dẫn và tự đặt ra cho mình câu hỏi: "Liệu bài này có thể làm bằng deque
hay không?".

Bài toán được mô tả như sau: Cho dãy số gồm \(n\) phần tử và có \(q\) truy vấn thuộc một
trong hai dạng sau:

• POFPUB x: Lấy phần tử đầu tiên của dãy và thêm nó vào cuối dãy. Lặp lại
  thao tác đó \(x\) lần (\(1 \le x \le 10^{9}\)).
• SUM l r: Tính tổng các phần tử nằm trên đoạn \([l, r]\) (\(1 \le l \le r \le n\)).

Input

Nhập từ file DEQUE.INP:

• Dòng đầu tiên chứa hai số nguyên dương \(n, q\) (\(1 \le n \le 10^{6},\ 1 \le q \le 10^{6}\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^{9}\)).
• \(q\) dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong hai dạng đã nêu.

Output

Ghi ra file DEQUE.OUT:

• Với mỗi truy vấn SUM l r, in ra tổng các phần tử trong đoạn \([l, r]\).

Example

5 5
2 3 2 4 5
POFPUB 2
SUM 3 5
POFPUB 2
SUM 3 5
SUM 1 5

10
9
16

3 3
1 1 1
POFPUB 17
SUM 1 2
SUM 1 3

2
3

Scoring

• \(30\%\) số test tương ứng với \(30\%\) số điểm: \(1 \le n, q \le 1000\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm: \(a_1 = a_2 = \cdots = a_n\).
• \(10\%\) số test tương ứng với \(10\%\) số điểm: với mọi truy vấn SUM, ta có \(l = 1, r = n\).
• \(40\%\) số test tương ứng với \(40\%\) số điểm còn lại: không có ràng buộc gì thêm.