Ông JOI làm việc tại Công ty Dược phẩm IOI. Tại đây, các nhà nghiên cứu đang bận rộn thử nghiệm để phát triển những loại thuốc xịt khử khuẩn mới.

Độ mạnh của một loại thuốc xịt khử khuẩn được định nghĩa như sau: nếu dùng một lần thuốc xịt có độ mạnh \(x\) lên một đĩa nuôi cấy có \(y\) vi khuẩn, số vi khuẩn còn lại sẽ là \(\left\lfloor y/x \right\rfloor\).

Một loại thuốc xịt mới có độ mạnh \(K\) vừa được phát triển. Để kiểm tra hiệu quả của nó, các nhà nghiên cứu tiến hành thí nghiệm trên \(N\) đĩa nuôi cấy, được đánh số từ \(1\) đến \(N\). Ban đầu, đĩa thứ \(i\) có \(C_i\) vi khuẩn. Trong thí nghiệm, họ lần lượt thực hiện \(Q\) thao tác. Mỗi thao tác thuộc một trong ba loại sau:

• Thao tác 1: Chọn một đĩa \(a\) và một số nguyên \(b\), rồi điều chỉnh số vi khuẩn trên đĩa \(a\) thành \(b\).
• Thao tác 2: Chọn hai số nguyên \(l\), \(r\) với \(1 \le l \le r \le N\), rồi xịt thuốc đúng một lần lên từng đĩa \(l, l+1, \ldots, r\).
• Thao tác 3: Chọn hai số nguyên \(l\), \(r\) với \(1 \le l \le r \le N\), tính tổng số vi khuẩn trên các đĩa \(l, l+1, \ldots, r\) và ghi lại kết quả.

Giả sử thuốc xịt mới hoạt động đúng như dự kiến. Hãy xác định tất cả các số được ghi lại bởi các thao tác loại 3.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu chứa ba số nguyên \(N\), \(Q\), \(K\), lần lượt là số đĩa nuôi cấy, số thao tác và độ mạnh của thuốc xịt.
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le N\)) chứa số nguyên \(C_i\), số vi khuẩn ban đầu trên đĩa thứ \(i\).
• Trong \(Q\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le Q\)) chứa ba số nguyên \(S_i\), \(T_i\), \(U_i\), mô tả thao tác thứ \(i\):
• Nếu \(S_i = 1\), đây là thao tác 1 với \(a = T_i\), \(b = U_i\).
• Nếu \(S_i = 2\), đây là thao tác 2 với \(l = T_i\), \(r = U_i\).
• Nếu \(S_i = 3\), đây là thao tác 3 với \(l = T_i\), \(r = U_i\).

Dữ liệu ra

Với mỗi thao tác loại 3, in số được ghi lại trên một dòng, theo đúng thứ tự thực hiện các thao tác. Số dòng kết quả bằng số thao tác loại 3.

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(1 \le Q \le 100\,000\).
• \(1 \le K \le 10\).
• \(0 \le C_i \le 1\,000\,000\,000\) (\(1 \le i \le N\)).
• \(1 \le S_i \le 3\) (\(1 \le i \le Q\)).
• Nếu \(S_i = 1\), thì \(1 \le T_i \le N\) và \(0 \le U_i \le 1\,000\,000\,000\).
• Nếu \(S_i = 2\) hoặc \(S_i = 3\), thì \(1 \le T_i \le U_i \le N\).

Phân nhóm

• Nhóm 1 (5 điểm)

• \(N \le 3\,000\).

• \(Q \le 3\,000\).

• Nhóm 2 (10 điểm)

• \(C_i \le 1\) (\(1 \le i \le N\)).

• Với mọi thao tác có \(S_i = 1\), ta có \(U_i \le 1\).

• Nhóm 3 (10 điểm)

• \(K = 1\).

• Nhóm 4 (75 điểm)

Không có ràng buộc bổ sung.

Ví dụ

5 10 3
1
2
8
1
3
1 2 5
2 3 5
3 2 5
2 1 4
1 3 2
3 3 5
1 2 4
2 1 2
1 1 4
3 1 5

8
3
8

15 10 3
25
87
32
89
24
99
57
88
10
57
65
42
66
98
13
3 9 12
1 7 15
3 2 9
2 1 14
3 10 13
1 10 6
2 14 14
1 7 96
3 14 15
3 10 12

174
444
76
23
41