Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(u_i\) \(v_i\) \(x_i\): Tăng mỗi phần tử từ vị trí \(u_i\) tới vị trí \(v_i\) lên \(x_i\) đơn vị.
• \(2\) \(u_i\) \(v_i\): Tìm giá trị lớn nhất trong các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\).

Yêu cầu: Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi ba số nguyên dương \(u_i\), \(v_i\) và \(x_i\) \((1 \leq u_i \leq v_i \leq N\), \(1 \leq x_i \leq 10^9)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \leq u_i \leq v_i \leq N)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3\), \(Q \leq 10^3\).
• Subtask \(2\) (\(20\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\), chỉ có các thao tác loại \(2\).
• Subtask \(3\) (\(20\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\), các thao tác \(1\) luôn được thực hiện trước các thao tác \(2\).
• Subtask \(4\) (\(30\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\).

Example

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

9
11

Cho dãy \(a\) gồm \(n\) phần tử là các số nguyên dương \(a_{1}, a_{2}, \ldots, a_{N}\). Cho \(q\) thao tác thực liện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(p\) \(x\): Chèn giá trị \(x\) vào giữa hai vị trí \(p - 1\) và \(p\) trong dãy \(a\) \((1 \leq p \leq t + 1\), với \(t\) là số phần tử hiện có trong dãy \(a\). Nếu \(p = t + 1\), chèn \(x\) vào cuối dãy \(a\).
• \(2\) \(u\) \(v\): Tìm giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\) \((1 \leq u \leq v \leq t\), với \(t\) là số phần tử hiện có trong dãy \(a).\)

Yêu cầu: Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(n, q\) \((1 \leq n, q \leq 10^{5})\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{N}\) \((a_{i} \leq 10^{9})\).
• \(q\) dòng tiếp theo, mỗi dòng thể hiện 1 truy vấn thuộc 1 trong 2 loại:/
  • \(1\) \(p\) \(x\) \((1 \leq p \leq n, 1 \leq x \leq 10^{9})\).
  • \(2\) \(u\) và \(v\) \((1 \leq u \leq v \leq n)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 10^{3}\).
• Subtask \(2\) (\(30\%\) số điểm): các thao tác \(1\) luôn được thực hiện trước các thao tác \(2\).
• Subtask \(3\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

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

3
5

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(p_i\) \(x_i\): Tăng phần tử ở vị trí \(p_i\) lên \(x_i\) đơn vị.
• \(2\) \(u_i\) \(v_i\): Tính tổng các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\).

Yêu cầu
Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi hai số nguyên dương \(p_i\) và \(x_i\) \((1 \leq p_i \leq N\), \(1 \leq x_i \leq 10^4)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \leq u_i \leq v_i \leq N)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra tổng các phần atử từ vị trí \(u\) tới vị trí \(v\) trên một dòng.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 10^3\), \(Q \leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\).

Example

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

32
24

Cho dãy \(a\) gồm \(n\) phần tử là các số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\). Cho \(q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(u_{i}\) \(v_{i}\) \(x_{i}\): Tăng mỗi phần tử từ vị trí \(u_{i}\) tới vị trí \(v_{i}\) lên \(x_{i}\) đơn vị.
• \(2\) \(u_{i}\) \(v_{i}\): Tính tổng các phần tử từ vị trí \(u_{i}\) tới vị trí \(v_{i}\).

Yêu cầu: thực hiện tất cả lần lượt \(q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(n, q\) \((1 \leq n, q \leq 10^{5})\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((a_{i} \leq 10^{9})\).
• \(q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi ba số nguyên dương \(u_{i}\), \(v_{i}\) và \(x_{i}\) \((1 \leq u_{i} \leq v_{i} \leq n, 1 \leq x_{i} \leq 10^{9})\). Số \(2\) theo sau bởi hai số nguyên dương \(u_{i}\) và \(v_{i}\) \((1 \leq u_{i} \leq v_{i} \leq n)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra tổng các phần tử từ vị trí \(u\) tới vị trí \(v\) trên một dòng.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n, q \leq 10^{3}\).
• Subtask \(2\) (\(30\%\) số điểm): mọi thao tác loại \(1\) có \(u = v\).
• Subtask \(3\) (\(40\%\) số điểm): không có rằng buộc gì thêm.

Example

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

13
30

Cho dãy số \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1, A_2, ..., A_N\), và \(Q\) truy vấn, truy vấn thứ \(i\) gồm \(2\) số nguyên dương \(L_i, R_i\) \((1 \leq L_i \leq R_i \leq N)\).

Yêu cầu: Với mỗi truy vấn thứ \(i\), hãy đếm số phần tử phân biệt trong khoảng từ \(L_i\) tới \(R_i\).

Input

• Gồm \(Q+2\) dòng:
• Dòng thứ nhất chứa hai số nguyên dương \(N, Q\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((1 \leq A_i \leq 10^6)\).
• \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(L_i, R_i\).

Output

• In ra \(Q\) dòng, dòng thứ \(i\) là số phần tử phân biệt trong khoảng từ \(L_i\) tới \(R_i\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N, Q \leq 10^5\).

Example

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

3
2
3

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(p_i\) \(x_i\): Thay giá trị ở vị trí \(p_i\) thành \(x_i\) (tức gán \(A_{p_i} = x_i\)).
• \(2\) \(u_i\) \(v_i\): Đếm số phần tử phân biệt và tính tổng các giá trị phân biệt trong đoạn từ \(u_i\) tới \(v_i\).

Yêu cầu: Thực hiện tất cả \(Q\) thao tác, và in ra \(2\) kết quả của thao tác loại \(2\).

Input

Gồm \(Q+2\) dòng:

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi hai số nguyên dương \(p_i\), và \(x_i\) \((1 \leq p_i\leq N\), \(1 \leq x_i \leq 10^9)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \leq u_i \leq v_i \leq N)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra \(2\) kết quả lần lượt là số phần tử phân biệt và tính tổng các giá trị phân biệt trong đoạn từ \(u\) tới \(v\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(30\)% số điểm có \(N \leq 2.10^3\), \(Q \leq 2.10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 5.10^4\), \(Q \leq 5.10^4\), chỉ có các thao tác loại \(2\).
• Subtask \(3\) (\(40\%\) số điểm): \(N \leq 5.10^4\), \(Q \leq 5.10^4\).

Example

 3 3
1 2 3
2 1 3
1 3 2
2 2 3 

3 6
1 2

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\) (\(A_i \leq 10^9\)). Cho \(Q\) thao tác thực liện lần lượt, thao tác thứ \(i\) sẽ có một trong \(4\) loại như sau:

• \(1\) \(p_i\) \(x_i\): Chèn giá trị \(x_i\) vào giữa hai vị trí \(p_i - 1\) và \(p_i\) trong dãy \(A\) (\(1 \leq x_i \leq 10^9\), \(1 \leq p_i \leq T + 1\), với \(T\) là số phần tử hiện có trong dãy \(A\). Nếu \(p_i = T + 1\), chèn \(x_i\) vào cuối dãy \(A\)).
• \(2\) \(u_i\) \(l_i\) \(v_i\): Chuyển tất cả các phần tử liên tiếp, bắt đầu từ vị trí \(u_i\), kết thúc ở vị trí \(u_i + l_i - 1\), chèn vào trước vị trí \(v_i\) trong số còn lại (\(1 \leq u_i \leq T\), \(u_i + l_i - 1 \leq T\) \(1 \leq v_i \leq T - l_i + 1\), với \(T\) là số phần tử hiện có trong dãy \(A\). Nếu \(v_i = T - l_i + 1\) thì chuyển tất cả các phần tử liên tiếp, bắt đầu từ vị trí \(u_i\), kết thúc ở vị trí \(u_i + l_i - 1\) vào cuối dãy \(A\)).
• \(3\) \(p_i\): Xoá phần tử ở vị trí \(p_i\) (\(1 \leq p_i \leq T\), với \(T\) là số phần tử hiện có trong dãy \(A\)).
• \(4\) \(u_i\) \(v_i\): Tìm giá trị lớn nhất trong các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\) (\(1 \leq u_i \leq v_i \leq T\), với \(T\) là số phần tử hiện có trong dãy \(A\)).

Yêu cầu
Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(4\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i\) chứa một trong \(4\) thao tác:
  • \(1\) \(p_i\) \(x_i\).
  • \(2\) \(u_i\) \(l_i\) \(v_i\).
  • \(3\) \(p_i\).
  • \(4\) \(u_i\) \(v_i\).

Output

• Với thao tác loại \(4\) có dạng \(4\) \(u\) \(v\), in ra giá trị lớn nhất trong các phần tử từ vị trí \(u\) tới vị trí \(v\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3\), \(Q \leq 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\), chỉ có các thao tác loại \(4\).
• Subtask \(3\) (\(40\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\).

Example

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

3
5

Cho số nguyên \(A\) gồm \(N\) phần tử gồm các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác được thực hiện lần lượt bao gồm gán, truy vấn và quay lại: (Gọi \(T\) là số lần gán. Ban đầu \(T = 0\)).

• Thao tác gán có dạng: \(1\) \(p\) \(val\): Gán \(A_p = val\) (\(1 \leq p \leq N\), \(1 \leq val \leq 10^9\)). Và \(T\) sẽ tăng lên \(1\).
• Thao tác truy vấn có dạng: \(2\) \(u\) \(v\) \(t\): Tìm giá trị lớn nhất trong đoạn từ \(u\) tới \(v\) sau phép gán lần thứ \(t\) (\(1 \leq u \leq v \leq N\), \(0 \leq t \leq T\). Nếu \(t = 0\) thì sẽ truy vấn trên mảng ban đầu trước khi thực hiện \(Q\) thao tác).
• Thao tác quay lại có dạng: \(3\) \(t\): Quay lại thời điểm sau lần gán thứ \(t\) (\(0 \leq t \leq T\). Nếu \(t = 0\) thì sẽ quay về mảng ban đầu trước khi thực hiện \(Q\) thao tác). Mọi thao tác gán sau thời điểm \(t\) sẽ bị xoá bỏ. Và \(T = t\).

Yêu cầu

Thực hiện lần lượt \(Q\) thao tác. Với thao tác loại \(2\) (Truy vấn), in ra kết quả.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên dương \(N\) và \(Q\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) (\(A_i \leq 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng là một thao tác gán, truy vấn hoặc quay lại: \(1\) \(p\) \(val\) hoặc \(2\) \(u\) \(v\) \(t\) hoặc \(3\) \(t\).

Kết quả

Với thao tác loại \(2\), in ra kết quả trên một dòng.

Ràng buộc

• \(30\%\) số test đầu tiên tương đương với \(30\%\) số điểm có \(N, Q \leq 10^3\).
• \(30\%\) số test tiếp theo tương đương với \(30\%\) số điểm có \(N, Q \leq 10^5\), không có thao tác \(3\), mọi thao tác \(2\) có \(t = T\)
• \(40\%\) số test còn lại tương đương với \(40\%\) số điểm có \(N, Q \leq 10^5\).

Ví dụ

Input:

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

Output:

7
8
6
7

Chúa đất vùng rừng AnLuuLand sau khi cho người anh hùng algorit chọn một vùng đất đã nhận ra sai lầm của mình khi cho phép phá rừng để làm nương rẫy, làm giảm diện tích rừng gây ảnh hưởng lớn đến biến đổi khí hậu.

Để khắc phục hậu quả, chúa đất quyết định trồng cây vào khu vực trống trước đó. Khu vực trống có thể xem là một hình chữ nhật gồm \(m\) hàng và \(n\) cột. Ban đầu trên này chưa hề có cây. Chúa trồng lên mỗi ô một cây xanh, ban đầu mỗi cây cao \(1 cm\). Mỗi tuần chúa đất ra một trong hai lệnh theo thứ tự:

• \(1\) \(x\) \(y\) \(u\) \(v\) \(c\): Bón phân cho một khu hình chữ nhật: \((x, y, u, v, c)\) bón cho mỗi cây có tọa độ thuộc vào hình chữ nhật có góc trái trên là \((x,y\)) và góc phải dưới là \((u,v)\) thêm \(c\) (gr) phân bón. Mỗi cây xanh khi nhận được \(1\) (gr) phân bón sẽ cao thêm \(1 (cm).\)
• \(2\) \(x\) \(y\): Cho biết chiều cao của cây ở ô \((x, y)\).

Sau \(k\) tuần thực hiện, chúa đất muốn biết về tình trạng độ cao của cây xanh ở các lệnh dạng \(2\) trong khu vực này. Nhiệm vụ của bạn thống kê điều đó cho chúa đất.

Input

• Dòng thứ nhất gồm 3 số \(m, n , k\)
• \(k\) dòng sau, mỗi dòng gồm một trong \(2\) lệnh có dạng:
  • \(1\) \(x\) \(y\) \(u\) \(v\) \(c\) (\(1 \leq x \leq u \leq m\), \(1 \leq y \leq v \leq n\), \(1 \leq c \leq 10^6\)).
  • \(2\) \(x\) \(y\) (\(1 \leq x \leq m\), \(1 \leq y \leq n\)).

Output

• Với mỗi lệnh dạng \(2\), in ra số nguyên duy nhất trên một dòng.

Scoring

• Subtask #1 (\(30\%\) số điểm): \(m * n \leq 10^3, k \leq 10^3\)
• Subtask #2 (\(30\%\) số điểm): \(m * n \leq 10^5, k \leq 10^5\), các lệnh loại \(1\) luôn thực hiện trước các lệnh loại \(2\).
• Subtask #3 (\(40\%\) số điểm): \(m * n \leq 10^5, k \leq 10^5\)

Example

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

2
4
2

Chúa đất vùng rừng AnLuuLand sau khi cho người anh hùng algorit chọn một vùng đất đã nhận ra sai lầm của mình khi cho phép phá rừng để làm nương rẫy, làm giảm diện tích rừng gây ảnh hưởng lớn đến biến đổi khí hậu.

Để khắc phục hậu quả, chúa đất quyết định trồng cây vào khu vực trống trước đó. Khu vực trống có thể xem là một hình chữ nhật gồm \(m\) hàng và \(n\) cột. Ban đầu trên này chưa hề có cây. Chúa trồng lên mỗi ô một cây xanh, ban đầu mỗi cây cao \(1cm\). Mỗi tuần chúa đất ra một trong hai lệnh theo thứ tự:

• \(1\space x\space y\space u\space v\space c\): Bón phân cho một khu hình chữ nhật: \((x,y,u,v,c)\) bón cho mỗi cây có tọa độ thuộc vào hình chữ nhật có góc trái trên là \((x,y)\) và góc phải dưới là \((u,v)\) thêm \(c(gr)\) phân bón. Mỗi cây xanh khi nhận được \(1(gr)\) phân bón sẽ cao thêm \(1(cm)\).
• \(2\space x\space y\): Cho biết chiều cao cây có toạ độ \((x,y)\).

Sau \(k\) tuần thực hiện, chúa đất muốn biết về tình trạng độ cao của cây xanh ở các lệnh dạng \(2\) trong khu vực này. Nhiệm vụ của bạn thống kê điều đó cho chúa đất.

Input

• Dòng thứ nhất gồm 3 số nguyên \(m,n,k\).
• \(k\) dòng tiếp theo, mỗi dòng gồm \(1\) trong \(2\) lệnh có dạng:
  1 x y u v c (\(1 \leq x \leq u \leq m,1 \leq y \leq v \leq n,1 \leq c \leq 10^6\)).
  2 x y (\(1 \leq x \leq m,1 \leq y \leq n\)).

Output

• Với mỗi lệnh dạng \(2\), in ra số nguyên duy nhất trên một dòng.

Constraints

• \(1 \leq k \leq 10^5\)
• \(1 \leq m,n \leq 10^5\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m*n \leq 10^3, k \leq 10^3\).
• Subtask \(2\) (\(20\%\) số điểm): \(m*n \leq 10^5, k \leq 10^5\).
• Subtask \(3\) (\(20\%\) số điểm): \(m,n \leq 10^5, k \leq 10^5\).
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

2
4
2

Chúa đất vùng rừng AnLuuLand sau khi cho người anh hùng algorit chọn một vùng đất đã nhận ra sai lầm của mình khi cho phép phá rừng để làm nương rẫy, làm giảm diện tích rừng gây ảnh hưởng lớn đến biến đổi khí hậu.

Để khắc phục hậu quả, chúa đất quyết định trồng cây vào khu vực trống trước đó. Khu vực trống có thể xem là một hình chữ nhật gồm \(m\) hàng và \(n\) cột. Ban đầu trên này chưa hề có cây. Chúa trồng lên mỗi ô một cây xanh, ban đầu mỗi cây cao \(1 cm\). Mỗi tuần chúa đất ra một trong hai lệnh theo thứ tự:

• \(1\) \(x\) \(y\) \(u\) \(v\) \(c\): Bón phân cho một khu hình chữ nhật: \((x, y, u, v, c)\) bón cho mỗi cây có tọa độ thuộc vào hình chữ nhật có góc trái trên là \((x,y\)) và góc phải dưới là \((u,v)\) thêm \(c\) (gr) phân bón. Mỗi cây xanh khi nhận được \(1\) (gr) phân bón sẽ cao thêm \(1 (cm).\)
• \(2\) \(x\) \(y\) \(u\) \(v\): Cho biết tổng tất cả chiều cao các cây có toạ độ thuộc hình chữ nhật có góc trái trên là \((x,y\)) và góc phải dưới là \((u,v)\).

Sau \(k\) tuần thực hiện, chúa đất muốn biết về tình trạng độ cao của cây xanh ở các lệnh dạng \(2\) trong khu vực này. Nhiệm vụ của bạn thống kê điều đó cho chúa đất.

Input

• Dòng thứ nhất gồm 3 số \(m, n , k\).
• \(k\) dòng sau, mỗi dòng gồm một trong \(2\) lệnh có dạng:
  • \(1\) \(x\) \(y\) \(u\) \(v\) \(c\) (\(1 \leq x \leq u \leq m\), \(1 \leq y \leq v \leq n\), \(1 \leq c \leq 10^3\)).
  • \(2\) \(x\) \(y\) \(u\) \(v\) (\(1 \leq x \leq u \leq m\), \(1 \leq y \leq v \leq n\)).

Output

• Với mỗi lệnh dạng \(2\), in ra số nguyên duy nhất trên một dòng.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(m, n \leq 10^2, k \leq 10^3\).
• Subtask \(2\) (\(20\%\) số điểm): \(m, n \leq 10^3, k \leq 10^5\), các lệnh loại \(1\) luôn thực hiện trước các lệnh loại \(2\).
• Subtask \(3\) (\(20\%\) số điểm): \(m, n \leq 10^3, k \leq 10^5\), các lệnh loại \(1\) luôn có \(x = u\), \(y = v\).
• Subtask \(4\) (\(20\%\) số điểm): \(m, n \leq 10^3, k \leq 10^5\), các lệnh loại \(2\) luôn có \(x = u\), \(y = v\).
• Subtask \(5\) (\(20\%\) số điểm): \(m, n \leq 10^3, k \leq 10^5\).

Example

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

18
4
48

Có \(N\) khách sạn trên một con đường. Với mỗi khách sạn bạn biết được số phòng còn trống. Nhiệm vụ của bạn là chỉ định các phòng khách sạn cho \(M\) nhóm khách du lịch. Tất cả các thành viên trong cùng một nhóm muốn trọ chung một khách sạn.

Các nhóm sẽ lần lượt đến và bạn biết số phòng yêu cầu của mỗi nhóm. Với mỗi nhóm, bạn luôn tìm khách sạn đầu tiên mà đủ số phòng trống và chỉ định nhóm đấy vào phòng này. Sau đó, số phòng trống của khách sạn này sẽ giảm đi.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N,M\): Số khách sạn và số nhóm. Các khách sạn được đánh số theo thứ tự từ \(1\) tới \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(H_1,H_2,...,H_N\) \((1≤H_i≤10^9)\): số phòng trống của mỗi khách sạn.
• Dòng cuối cùng gồm \(M\) số nguyên dương \(R_1,R_2,...,R_M\) \((1≤Ri≤10^9)\): số phòng trống mà mỗi nhóm yêu cầu.

Output

• In ra \(M\) số nguyên là chỉ số của khách sạn được phân cho mỗi nhóm. Nếu nhóm nào đó không được chỉ định vào khách sạn (do không tìm được), in ra số \(0\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N,Q≤2.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N,Q≤2.10^5\).

Example

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

3 5 0 1 1

Cho một mảng gồm \(N\) phần tử là các số nguyên. Nhiệm vụ của bạn là xoá phần tử trong mảng và báo cáo phần tử đã bị xoá.

Input

• Dòng đầu tiên gồm số nguyên dương \(N\): kích thước mảng ban đầu. Sau khi xoá một phần tử, các phần tử còn lại sẽ được đánh số lại từ \(1\) tới \(k\), với \(k\) là kích thước mảng hiện tại.
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1,A_2,...,A_N\) \((1≤A_i≤10^9)\).
• Dòng cuối cùng gồm \(N\) số nguyên dương \(P_1,P_2,...,P_N\) \((1≤P_i≤N−i+1)\): vị trí của phần tử bị xoá.

Output

• In ra phần tử bị xoá theo thứ tự.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N,Q≤2.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N,Q≤2.10^5\).

Example

5
2 6 1 4 2
3 1 3 1 1 

1 2 2 6 4

Một công ty có \(N\) nhân viên với với mức lương nhất định. Nhiệm vụ của bạn là theo dõi mức lương và thực hiện truy vấn.

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\) là số nhân viên và số truy vấn. Các nhân viên được đánh số từ \(1\) tới \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) là lương của mỗi người.
• \(Q\) dòng tiếp theo, mỗi dòng gồm một truy vấn thuộc một trong hai dạng sau:
• \(!\) \(k\) \(x\): thay đổi lương của người thứ \(k\) thành \(x\).
• \(?\) \(a\) \(b\): đếm số người có mức lương từ \(a\) tới \(b\).

Output

• In ra kết quả cho truy vấn \(?\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N, Q \leq 2.10^3\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).
• Subtask \(2\) (\(30\%\) số điểm): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^5\) với \(\forall i, 1 \leq i \leq N\).
• Subtask \(3\) (\(40\%\) số điểm): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).

Example

5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3 

3
2

Cho một mảng bao gồm \(N\) số nguyên. Một số phần tử sẽ được cập nhật, và sau mỗi lần cập nhật, nhiệm vụ của bạn là tìm tổng lớn nhất của tất cả các đoạn con (liên tiếp) trong mảng.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, Q\): Kích thước của mảng và số truy vấn.
• Dòng thứ hai gồm \(N\) số nguyên \(A_1, A_2, ..., A_N\) \((|A_i| \leq 10^9)\).
• \(Q\) dòng tiếp theo, mỗi dòng có hai số nguyên \(k\) và \(x\) \((1 \leq k \leq N, |x| \leq 10^9)\): thay đổi phần tử \(k\) thành giá trị \(x\).

Output

• Sau mỗi lần cập nhật, in ra tổng lớn nhất của tất cả các đoạn con trong mảng. Các mảng con rỗng (với tổng bằng 0) vẫn được tính.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 2.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N, Q \leq 2.10^5\).

Example

5 3
1 2 -3 5 -1
2 6
3 1
2 -2 

9
13
6

Cho mảng gồm \(N\) phần tử là các số nguyên. Nhiệm vụ của bạn là xử lý các loại truy vấn sau:

• \(1\) \(a\) \(b\) \(x\) : Tăng các phần tử từ \(a\) đến \(b\) lên \(x\).
• \(2\) \(a\) \(b\) \(x\) : Thay đổi tất cả các phần tử từ \(a\) đến \(b\) thành \(x\).
• \(3\) \(a\) \(b\) : Tính tổng các phần tử từ \(a\) đến \(b\).

Input

• Dòng thứ nhất gồm hai số nguyên \(N, Q\) là kích thước mảng và số truy vấn.
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((1 \leq A_i \leq 10^6)\).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn thuộc một trong ba dạng sau:
  • \(1\) \(a\) \(b\) \(x\) \((1 \leq a \leq b \leq N, 1 \leq x \leq 10^6)\).
  • \(2\) \(a\) \(b\) \(x\) \((1 \leq a \leq b \leq N, 1 \leq x \leq 10^6)\).
  • \(3\) \(a\) \(b\) \((1 \leq a \leq b \leq N)\).

Output

• In ra kết quả cho các truy vấn \(3\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 2.10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N, Q \leq 2.10^5\).

Example

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

7
11
15

Cho một mảng gồm \(N\) phần tử. Nhiệm vụ của bạn là thực hiện các truy vấn sau:

• \(1\) \(a\) \(b\): Tăng phần tử đầu tiên trong đoạn \([a, b]\) lên \(1\), phần tử thứ hai lên \(2\), phần tử thứ ba lên \(3\), \(\ldots\)
• \(2\) \(a\) \(b\): Tính tổng các phần tử trong đoạn \([a, b]\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\) \((N, Q \leq 2 \times 10^{5})\): kích thước mảng và số truy vấn.
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_{1}, A_{2}, \ldots, A_{N}\) \((1 \leq A_{i} \leq 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 sau:
  • \(1\) \(a\) \(b\) \((1 \leq a \leq b \leq N)\).
  • \(2\) \(a\) \(b\) \((1 \leq a \leq b \leq N)\).

Output

• In ra kết quả cho các truy vấn \(2\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 2 \times 10^{3}\).
• Subtask \(2\) (\(50\%\) số điểm): không có rằng buộc gì thêm.

Example

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

17
32

Cho một tập các mảng mà ban đầu chỉ có một mảng. Nhiệm vụ của bạn là thực hiện các truy vấn sau:

• \(1\) \(k\) \(a\) \(x\): Thay đổi phần tử thứ \(a\) ở mảng thứ \(k\) thành \(x\).
• \(2\) \(k\) \(a\) \(b\): Tính tổng các phần tử trong đoạn \([a, b]\) ở mảng \(k\).
• \(3\) \(k\): Tạo một bản sao của mảng \(k\) và đưa vào cuối tập các mảng.

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\): kích thước từng mảng và số truy vấn.
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((1 \leq A_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong ba dạng sau:
  • \(1\) \(k\) \(a\) \(b\) \((1 \leq k \leq\) số mảng hiện tại, \(1 \leq a \leq b \leq N)\).
  • \(2\) \(k\) \(a\) \(b\) \((1 \leq k \leq\) số mảng hiện tại, \(1 \leq a \leq b \leq N)\).
  • \(3\) \(k\) (\(1 \leq k \leq\) số mảng hiện tại).

Output

• In ra kết quả cho các truy vấn \(2\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N, Q \leq 2.10^3\).
• Subtask \(2\) (\(50\%\) số điểm) \(N, Q \leq 2.10^5\).-

Example

5 6
2 3 1 2 5
3 1
2 1 1 5
2 2 1 5
1 2 2 5
2 1 1 5
2 2 1 5 

13
13
13
15

Nông dân V.H.A có \(N\) khu vườn để chăn nuôi chú gà SPyofgame. Các khu vườn được kết nối với nhau bằng \(N-1\) con đường hai chiều, tức là chỉ có đúng một đường đi giữa hai khu vườn (giàu mà keo đây mà). Vì là một con gà béo tham lam nên SPyofgame đã đòi hỏi trên đường các con đường luôn phải có đồ ăn cho nó. Vì thế, V.H.A đã phải thực hiện các công việc sau:

1. P x y: V.H.A sẽ chọn ra hai khu vườn và bỏ 1 nồi thóc dọc theo con đường nối hai khu vườn.
2. Q x y: V.H.A sẽ phải trả lời trên đoạn đường nối hai khu vườn có bao nhiêu nồi thóc.

Input:

• Dòng đầu tiên chứa hai số nguyên \(N, M (1 \leq M \leq 100000, 2 \leq N \leq 100000).\)
• \(N-1\) dòng tiếp theo, mỗi dòng là hai số nguyên thể hiện hai đầu nối của một con đường.
• \(M\) dòng cuối cùng, mỗi dòng là một truy vấn theo cấu trúc P x y hoặc Q x y \((1 \leq x,y \leq N)\).

Output:

• Mỗi dòng là câu trả lời cho mỗi truy vấn Q theo thứ tự.

Example

3 3
1 2
2 3
P 1 3
Q 2 3
Q 1 3

1
2

Chúa đất vùng rừng AnLuuLand sau khi cho người anh hùng algorit chọn một vùng đất đã nhận ra sai lầm của mình khi cho phép phá rừng để làm nương rẫy, làm giảm diện tích rừng gây ảnh hưởng lớn đến biến đổi khí hậu.

Để khắc phục hậu quả, chúa đất quyết định trồng cây vào khu vực trống trước đó. Khu vực trống có thể xem là một hình chữ nhật gồm \(m\) hàng và \(n\) cột. Ban đầu trên này chưa hề có cây. Chúa trồng lên mỗi ô một cây xanh, ban đầu mỗi cây cao \(1cm\). Mỗi tuần chúa đất ra một trong hai lệnh theo thứ tự:

• \(1\space x\space y\space u\space v\space c\): Bón phân cho một khu hình chữ nhật: \((x,y,u,v,c)\) bón cho mỗi cây có tọa độ thuộc vào hình chữ nhật có góc trái trên là \((x,y)\) và góc phải dưới là \((u,v)\) thêm \(c(gr)\) phân bón. Mỗi cây xanh khi nhận được \(1(gr)\) phân bón sẽ cao thêm \(1(cm)\).
• \(2\space x\space y\space u\space v\): Cho biết tổng tất cả chiều cao các cây có toạ độ thuộc hình chữ nhật có góc trái trên là \((x,y)\) và góc phải dưới là \((u,v)\).

Sau \(k\) tuần thực hiện, chúa đất muốn biết về tình trạng độ cao của cây xanh ở các lệnh dạng \(2\) trong khu vực này. Nhiệm vụ của bạn thống kê điều đó cho chúa đất.

Input

• Dòng thứ nhất gồm 3 số \(m,n,k\).
• \(k\) dòng sau, mỗi dòng gồm một trong \(2\) lệnh có dạng:
  • \(1\space x\space y\space u\space v\space c\) \((1≤x≤u≤m, 1≤y≤v≤n, 1≤c≤10^3)\).
  • \(2\space x\space y\space u\space v\) \((1≤x≤u≤m, 1≤y≤v≤n,)\).

Output

• Với mỗi lệnh dạng \(2\), in ra số nguyên duy nhất trên một dòng.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(m,n≤10^2,k≤10^3\).
• Subtask \(2\) (\(15\%\) số điểm): \(m,n≤10^3,k≤10^5\), các lệnh loại \(1\) luôn được thực hiện trước các câu lệnh loại \(2\).
• Subtask \(3\) (\(10\%\) số điểm): \(m,n≤10^3,k≤10^5\), các lệnh loại \(1\) luôn có \(x = u, y = v\).
• Subtask \(4\) (\(10\%\) số điểm): \(m,n≤10^3,k≤10^5\), các lệnh loại \(2\) luôn có \(x = u, y = v\).
• Subtask \(5\) (\(15\%\) số điểm): \(m,n≤10^3,k≤10^5\).
• Subtask \(6\) (\(15\%\) số điểm): \(m,n≤10^5,k≤10^5\).

Example

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

18
4
48

Jian-Jia lên kế hoạch cho kỳ nghỉ tiếp theo tại Đài Loan. Trong kỳ nghỉ này, Jian-Jia di chuyển từ thành phố này đến thành phố khác và thăm các điểm du lịch tại các thành phố.

Có \(N\) thành phố tại Đài Loan, tất cả nằm dọc theo một con đường cao tốc. Các thành phố được đánh số liên tiếp bắt đầu từ \(0\) đến \(N-1\). Thành phố \(i\) với \(0 < i < N-1\), liền kề với thành phố \(i-1\) và \(i+1\). Thành phố duy nhất liền kề với thành phố \(0\) là thành phố \(1\) và thành phố duy nhất liền kề với thành phố \(N-1\) là thành phố \(N-2\).

Mỗi thành phố có một số điểm du lịch. Jian-Jia có \(d\) ngày cho kỳ nghỉ và lên kế hoạch để thăm được nhiều điểm du lịch nhất. Jian-Jia đã chọn một thành phố làm thành phố xuất phát cho kỳ nghỉ của mình. Mỗi ngày trong kỳ nghỉ, Jian-Jia hoặc di chuyển đến thành phố liền kề hoặc đi thăm tất cả các điểm du lịch của thành phố mà nó đang dừng chân, nhưng không thực hiện cả hai điều này. Jian-Jia sẽ không bao giờ thăm các điểm du lịch trong
cùng một thành phố hai lần ngay cả khi Jian-Jia ở trong thành phố nhiều lần. Hãy giúp Jian-Jia lên kế hoạch cho kỳ nghỉ của mình để thăm được nhiều điểm du lịch khác nhau nhất.

Ví dụ:

Giả sử Jian-Jia có \(7\) ngày cho kỳ nghỉ, có \(5\) thành phố (được liệt kê trong bảng dưới đây) và Jian-Jia xuất phát từ thành phố \(2\). Trong ngày thứ nhất, Jian-Jia thăm quan \(20\) điểm du lịch ở thành phố \(2\). Trong ngày thứ haiJian-Jia di chuyển từ thành phố \(2\) đến thành phố \(3\) và trong ngày thứ ba thăm \(30\) điểm du lịch ở thành phố \(3\). Jian-Jia dành ba ngày tiếp theo để di chuyển từ thành phố \(3\) đến thành phố \(0\) và thăm \(10\) điểm du lịch ở thành phố \(0\) vào ngày thứ bảy. Tổng số điểm du lịch mà Jian-Jia thăm là \(20 + 30 + 10 = 60\), đó là số lượng lớn nhất các điểm du lịch mà Jian-Jia có thể thăm trong \(7\) ngày nếu xuất phát từ thành phố \(2\).

Yêu cầu: Tính số lượng nhiều nhất các điểm du lịch mà Jian-Jia có thể thăm

Input

• Dòng thứ nhất: \(N, start, d\) (\(N:\) là số thành phố, \(start:\) thành phố xuất phát, \(d:\) số lượng ngày nghỉ)
• Dòng thứ hai: \(attraction[0], . . . , attraction[N − 1]\). (\(attraction[i]:\) là số lượng điểm du lịch tại thành phố \(i\), với \(0 \leq i \leq N-1\)).

Output

• In ra một số duy nhất là số lượng nhiều nhất các điểm du lịch mà Jian-Jia có thể thăm.

Scoring

• Trong tất cả các test, \(0 \leq d \leq 2n + ⌊n/2⌋\), và số điểm du lịch tại mỗi thành phố là không âm.
• Subtask \(1\) (\(7\%\) số điểm): \(2 \leq N \leq 20\), số điểm du lịch lớn nhất trong một thành phố là \(10^9\).
• Subtask \(2\) (\(23\%\) số điểm): \(2 \leq N \leq 10^5\), số điểm du lịch lớn nhất trong một thành phố là \(10^2\), thành phố xuất phát luôn là \(0\).
• Subtask \(3\) (\(17\%\) số điểm): \(2 \leq N \leq 3.10^3\), số điểm du lịch lớn nhất trong một thành phố là \(10^9\).
• Subtask \(4\) (\(53\%\) số điểm): \(2 \leq N \leq 10^5\), số điểm du lịch lớn nhất trong một thành phố là \(10^9\).

Example

5 2 7
10 2 20 30 1

60

Jian-Jia đang xây dựng bức tường bằng cách xếp các viên gạch có cùng kích thước. Bức tường bao gồm \(N\) cột gạch, được đánh số từ 0 đến \(N-1\) từ trái qua phải. Các cột có thể có độ cao khác nhau. Độ cao của một cột là số viên gạch trên nó.

Jian-Jia xây dựng bức tường theo cách sau. Thoạt tiên, không có viên gạch nào trên mỗi cột. Sau đó, Jian-Jia thực hiện \(K\) giai đoạn thêm hoặc bớt các viên gạch. Quá trình xây dựng sẽ chấm dứt khi tất cả \(K\) giai đoạn được hoàn thành. Trong mỗi giai đoạn, Jian-Jia được cho biết một dãy các cột gạch liên tiếp và chiều cao \(H\), và nó cần thực hiện thủ tục sau đây:

• Trong giai đoạn thêm, Jian-Jia thêm các viên gạch vào các cột trong dãy cột đã cho mà có ít hơn \(H\) viên gạch sao cho chúng chứa đúng \(H\) viên gạch. Jian-Jia không làm gì với những cột có nhiều hơn hoặc bằng \(H\) viên gạch.

• Trong giai đoạn bớt, Jian-Jia loại bớt các viên gạch từ các cột trong dãy cột đã cho mà chứa nhiều hơn \(H\) viên gạch, sao cho chúng chứa đúng \(H\) viên gạch. Jian-Jia không làm gì với những cột có ít hơn hoặc bằng \(H\) viên gạch.

Nhiệm vụ của bạn là xác định hình dạng cuối cùng của bức tường.

Ví dụ:

Giả sử là có 10 cột gạch và 6 giai đoạn xây dựng tường. Các dãy cột trong bảng sau đây là kể cả hai cột đầu mút. Sơ đồ của bức tường sau mỗi giai đoạn được mô tả ở phía dưới.

Do khởi đầu tất cả các cột đều rỗng, sau giai đoạn 0 các cột từ 1 đến 8 đều có 4 viên gạch. Cột 0 và 9 vẫn là rỗng. Trong giai đoạn 1, cần bớt các viên gạch khỏi các cột từ 4 đến 8 cho đến khi mỗi cột này còn đúng 1 viên gạch, và cột 9 vẫn là rỗng. Các cột từ 0 đến 3, do không thuộc dãy cột được chọn, nên chúng không thay đổi. Giai đoạn 2 không dẫn đến thay đổi gì do các cột từ 3 đến 6 không chứa nhiều hơn 5 viên gạch. Sau giai đoạn 3 số lượng gạch trong các cột 0, 4, và 5 tăng lên thành 3. Có 5 viên gạch trong cột 2 sau giai đoạn 4. Giai đoạn 5 loại tất cả các viên gạch trong các cột 6 và 7.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(N\) và \(K\) là số lượng cột trong bức tường và số giai đoạn.
• \(K\) dòng tiếp theo, dòng thứ \(i\) chứa bốn số nguyên \(Op_i\), \(Left_i\), \(Right_i\), \(Height_i\). Với \(\forall i, 0 \leq i \leq N-1\):
  • \(Op_i\): là kiểu của giai đoạn \(i\). 1 nếu là giai đoạn thêm và 2 nếu là giai đoạn bớt.
  • \(Left_i\), \(Right_i\): giới hạn dãy cột ở giai đoạn \(i\) \((0 \leq Left_i \leq Right_i \leq N-1)\).
  • \(Height_i\): là thông số chiều cao trong giai đoạn \(i\).

Output

• Gồm \(N\) số nguyên, số thứ \(i+1\) là chiều cao của cột thứ \(i\) sau khi thực hiện \(K\) giai đoạn, với \(\forall i, 0 \leq i \leq N-1\).

Scoring

Trong mọi Subtasks, chiều cao trong mọi giai đoạn là số nguyên không âm nhỏ hơn hoặc bằng \(10^5\).

• Subtask \(1\) (\(8\) điểm): \(N \leq 10^4\), \(K \leq 5.10^3\).
• Subtask \(2\) (\(24\) điểm): \(N \leq 10^5\), \(K \leq 5.10^5\), tất cả các giai đoạn thêm xuất hiện trước mọi giai đoạn bớt.
• Subtask \(3\) (\(29\) điểm): \(N \leq 10^5\), \(K \leq 5.10^5\).
• Subtask \(4\) (\(39\) điểm): \(N \leq 2.10^6\), \(K \leq 5.10^5\).

Example

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

3 4 5 4 3 3 0 0 1 0