Cấu trúc dữ liệu là nội dung rất quan trọng trong khoa học máy tính. Trong chương trình giảng dạy cho các lớp chuyên Tin, nội dung cấu trúc dữ liệu được đưa vào nhiều chuyên đề. Một bài toán thao tác trên bảng được dùng để kiểm tra khả năng tổ chức dữ liệu và linh hoạt trong xử lí như sau: Cho một bảng số gồm \(m\) hàng và \(n\) cột, các hàng được đánh số từ trên xuống dưới từ \(1\) đến \(m\), các cột được đánh số từ trái sang phải từ \(1\) đến \(n\), ô nằm giao giữa hàng \(i\) (\(1 \leq i \leq m\)) và cột \(j\) (\(1 \leq j \leq n\)) gọi là ô \((i, j)\) và có giá trị ban đầu là \(a_{ij}\). Cần thực hiện \(Q\) thao tác trên bảng số, mỗi thao tác thuộc một trong hai loại:

• Thao tác loại \(1\) có dạng: \(1 \ x \ y \ u \ v \ w\) có nghĩa là với mỗi ô nằm trong hình chữ nhật có ô trái trên là ô \((x, y)\) và ô phải dưới là ô \((u, v)\) sẽ được cộng thêm \(w\);
• Thao tác loại \(2\) có dạng: \(2 \ x \ y \ u \ v\) có nghĩa là cần đưa ra tổng giá trị của các ô nằm trong hình chữ nhật có ô trái trên là ô \((x, y)\) và ô phải dưới là ô \((u, v)\).

Input

• Dòng đầu chứa ba số nguyên dương \(m\), \(n\), \(Q\) (\(m, n \leq 500\));
• Dòng thứ \(i\) (\(1 \leq i \leq m\)) trong \(m\) dòng sau chứa \(n\) số nguyên không âm \(a_{i1}, a_{i2}, \ldots, a_{in}\) (\(a_{ij} \leq 10 ^ 9\)).
• Dòng thứ \(k\) (\(1 \leq k \leq Q\)) trong \(Q\) dòng sau mô tả thao tác thứ \(k\). Nếu là thao tác loại \(1\), dòng gồm năm số nguyên \(1\), \(x\), \(y\), \(u\), \(v\), \(w\) (\(1 \leq x \leq u \leq m\); \(1 \leq y \leq v \leq n\); \(0 \leq w \leq 10 ^ 9\)), nếu là thao tác loại \(2\), dòng gồm bốn số nguyên \(2\), \(x\), \(y\), \(u\), \(v\) (\(1 \leq x \leq u \leq m\); \(1 \leq y \leq v \leq n\)).

Output

• Ghi ra thiết bị chuẩn một số dòng, mỗi dòng tương ứng là câu trả lời cho thao tác loại \(2\) lần lượt xuất hiện trong file dữ liệu vào.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(Q \leq 100\);
• Subtask \(2\) (\(30\%\) số điểm): \(Q \leq 10 ^ 5\) và tất cả thao tác loại \(1\) xuất hiện trước các thao tác loại \(2\);
• Subtask \(3\) (\(20\%\) số điểm): \(Q \leq 10 ^ 4\);
• Subtask \(4\) (\(20\%\) số điểm): \(Q \leq 10 ^ 5\).

Example

2 3 3
0 0 0
0 0 0
2 1 1 2 3
1 1 1 2 3 1
2 1 1 2 2      

0
4        

Bài toán dưới đây có rất nhiều cách tiếp cận, bài toán rất phù hợp để giảng dạy và kiểm tra về nội dung các chiến lược phân tích thiết kế thuật toán, bài toán như sau:
Có \(n\) hộp bi xếp thành một hàng, hộp thứ \(i (1\le i\le n)\) có \(a_{i} (0\le a_i\le 10^9)\) viên \(b_{i}\). Mỗi lượt, người chơi được chọn một đoạn gồm các hộp bi liên tiếp vẫn còn bi và lấy ra từ mỗi hộp một viên bi. Người chơi được thực hiện không quá r lượt và mong muốn làm cho nhiều hộp rỗng nhất.

Input

• Dòng đầu chứa hai số nguyên dương \(n,r\);
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_{1},a_{2},…,a_{n}\).

Output

• Ghi ra file thiết bị ra chuẩn một số nguyên là số lượng hộp rỗng nhiều nhất đạt được nếu người chơi biết chiến lược chơi tối ưu.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n\le 10, r=1\);
• Subtask \(2\) (\(30\%\) số điểm): \(n\le 10, r\le 5\);
• Subtask \(3\) (\(30\%\) số điểm): \(n\le 200, r\le 200\);
• Subtask \(4\) (\(20\%\) số điểm):\(n\le 200, r\le 10^9\);
• Subtask \(5\) (\(10\%\) số điểm): \(n\le 2000, r\le 10^9\).

Example

6 2
0 2 1 2 2 3

4

Pax Thiên là người yêu thích điện ảnh và anh ấy có cả một bộ sưu tập các bộ phim Hollywood. Anh sử dụng một ngăn xếp (stack) để quản lý các đĩa phim, trong đó các bộ phim được xếp chồng từ dưới lên trên.

Mỗi lần Pax Thiên muốn xem một bộ phim, anh sẽ lấy bộ phim đó ra khỏi ngăn xếp, xem xong rồi đặt lại bộ phim lên đỉnh ngăn xếp. Sau nhiều lần xem, thứ tự các bộ phim trong ngăn xếp bị xáo trộn, khiến anh khó xác định vị trí của từng bộ phim.

Pax Thiên nhờ bạn viết một chương trình giúp quản lý ngăn xếp phim để dễ dàng xác định vị trí của các bộ phim sau mỗi lần xem.

Input

• Dòng đầu tiên chứa hai số nguyên N và M:

• N là số lượng bộ phim.

• M là số lần Pax Thiên xem phim.
• Các bộ phim được đánh số từ 1 đến N.

• Ban đầu, các bộ phim được xếp từ trên xuống dưới trong ngăn xếp:

  • Đỉnh ngăn xếp là phim 1
  • Đáy ngăn xếp là phim N
  • Giới hạn:
    1 ≤ N, M ≤ 100000

• Dòng thứ hai chứa M số nguyên, mỗi số là mã bộ phim mà Pax Thiên lần lượt xem.

Output

• In ra một dòng gồm M số.
• Số thứ i là vị trí của bộ phim thứ i mà Pax Thiên xem, tính từ đỉnh ngăn xếp xuống dưới, trước khi bộ phim đó được lấy ra.

Ví dụ

5 3
4 4 5

4 1 5

Nhân dịp Noel, đội tuyển tin xếp thành một hàng ngang để chụp ảnh. Có n học sinh đứng chụp ảnh (1 ≤ n ≤ 10^5), được đánh số từ trái sang phải là 1, 2, ..., n.

Chiều cao của học sinh thứ i là h_i. Đặc biệt, không có hai học sinh nào có cùng chiều cao.

Một vị trí i được gọi là không cân đối nếu hai giá trị L_i và R_i chênh lệch nhau hơn 2 lần, trong đó:

• L_i là số học sinh cao hơn học sinh i đứng bên trái
• R_i là số học sinh cao hơn học sinh i đứng bên phải

Yêu cầu

Hãy đếm xem trong bức ảnh có bao nhiêu vị trí không cân đối.

Input

• Dòng đầu tiên chứa số nguyên dương n (n ≤ 10^5)
• n dòng tiếp theo, mỗi dòng chứa một số nguyên:
• h_1, h_2, ..., h_n (0 ≤ h_i ≤ 10^9)

Output

• In ra một số nguyên duy nhất — số lượng vị trí không cân đối trong bức ảnh

Subtasks

• Subtask 1: n ≤ 5000
• Subtask 2: n ≤ 10^5

Ví dụ

7
34
6
23
0
5
99
2

3

Trung vị của một dãy \(k\) số là số thứ \(k \div 2\) của dãy số sau khi sắp xếp tăng dần (các số được đánh chỉ số từ \(0\) đến \(k - 1\)). Ví dụ dãy số \((7, 3, 2, 6)\) có trung vị là \(6\), dãy \((5, 4, 8)\) có trung vị là \(5\).

Cho một dãy \(N\) \((1 \le N \le 100000)\) số nguyên dương không quá \(10^9\), hãy đếm xem có bao nhiêu dãy con (là một số phần tử liên tiếp) có trung vị lớn hơn hoặc bằng \(X\) \((1 \le X \le 10^9)\).

Input

• Dòng \(1\): Ghi số \(N\) và \(X\).
• \(N\) dòng sau, dòng \(i\) ghi số thứ \(i - 1\) trong dãy số.

Output

• Ghi một số nguyên duy nhất là kết quả bài toán.

4 6
10
5
6
2

7