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

Ban đầu, tất cả các cột đều không có gạch. Sau đó, Jian-Jia thực hiện \(k\) giai đoạn thêm hoặc bớt gạch. Quá trình xây dựng kết thúc khi hoàn thành cả \(k\) giai đoạn. Trong mỗi giai đoạn, Jian-Jia được cho một dãy cột liên tiếp và một độ cao \(h\), rồi thực hiện như sau:

• Trong giai đoạn thêm, với mỗi cột thuộc dãy đã cho có ít hơn \(h\) viên gạch, Jian-Jia thêm gạch để cột có đúng \(h\) viên. Các cột có từ \(h\) viên trở lên không thay đổi.
• Trong giai đoạn bớt, với mỗi cột thuộc dãy đã cho có nhiều hơn \(h\) viên gạch, Jian-Jia bớt gạch để cột có đúng \(h\) viên. Các cột có từ \(h\) viên trở xuống không thay đổi.

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ử có 10 cột gạch và 6 giai đoạn xây dựng. Mọi dãy cột trong bảng dưới đây đều bao gồm cả hai đầu mút.

Giai đoạn  Kiểu  Dãy cột        Độ cao
0          thêm  từ cột 1 đến 8  4
1          bớt   từ cột 4 đến 9  1
2          bớt   từ cột 3 đến 6  5
3          thêm  từ cột 0 đến 5  3
4          thêm  cột 2           5
5          bớt   từ cột 6 đến 7  0

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

Các hình dưới đây lần lượt mô tả bức tường sau từng giai đoạn.

Sau giai đoạn 0:

Sau giai đoạn 1:

Sau giai đoạn 2 (không thay đổi):

Sau giai đoạn 3:

Sau giai đoạn 4:

Sau giai đoạn 5:

Nhiệm vụ

Cho mô tả của \(k\) giai đoạn, hãy tính số viên gạch trong mỗi cột sau khi hoàn thành tất cả các giai đoạn. Bạn cần cài đặt hàm buildWall(n, k, op, left, right, height, finalHeight).

• n: số cột của bức tường.
• k: số giai đoạn.
• op: mảng độ dài \(k\); op[i] là kiểu của giai đoạn \(i\): 1 là thêm, 2 là bớt, với \(0 \le i \le k-1\).
• left, right: hai mảng độ dài \(k\); dãy cột của giai đoạn \(i\) bắt đầu tại left[i] và kết thúc tại right[i], bao gồm cả hai đầu mút, với \(0 \le i \le k-1\). Luôn có left[i] \(\le\) right[i].
• height: mảng độ dài \(k\); height[i] là thông số độ cao của giai đoạn \(i\), với \(0 \le i \le k-1\).
• finalHeight: mảng độ dài \(n\); bạn phải gán số viên gạch cuối cùng trong cột \(i\) vào finalHeight[i], với \(0 \le i \le n-1\).

Các subtasks

Trong mọi subtask, thông số độ cao ở mọi giai đoạn là số nguyên không âm không lớn hơn \(100\,000\).

Chi tiết cài đặt

Bạn phải nộp đúng một tệp có tên wall.c, wall.cpp hoặc wall.pas, cài đặt chương trình con theo đặc tả trên và chữ ký dưới đây. Với C/C++, bạn phải nạp tệp tiêu đề wall.h.

C/C++:

void buildWall(int n, int k, int op[], int left[], int right[],
int height[], int finalHeight[]);

Pascal:

procedure buildWall(n, k : longint; op, left, right, height :
array of longint; var finalHeight : array of longint);

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng 1: n, k.
• Dòng \(2+i\), với \(0 \le i \le k-1\): op[i], left[i], right[i], height[i].