Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Hảo Hảo, cảm nhận từng giây hạnh phúc

Bạn là chủ một hệ thống nhà hàng chuyên bán mì ăn liền. Tại sao lại là mì ăn liền, đó là vì "dẫu thời gian mang đến nhiều đổi thay, những điều tuyệt vời vẫn còn đó trên mảnh đất này. Hảo Hảo, cảm nhận từng giây hạnh phúc".

Khi xem các quảng cáo mì ăn liền, ta đều thấy cả nhà cùng ngồi ăn mì và cười hạnh phúc, hay là người mẹ đi làm và mua mì về thì cả nhà cùng nhau reo hò. Mì thường được làm từ "trứng vàng" (~\le~15g/1kg) hay khoai tây (~\approx~20g/1kg) rất tốt cho sức khỏe, trong khi đó thành phần sắn thì chỉ là thành phần phụ (~\approx~900g/1kg). Nhà hàng của bạn có n gói mì đủ loại, mỗi gói có độ ngon là ~a_i~ (~|a_i|\le10^9~). Bạn cần xử lý 2 loại truy vấn như sau:

  • Loại 1 có dạng ~1~ ~x~ ~y~: Nấu gói mì ở vị trí thứ ~x~ và mua gói mì có độ ngon ~y~ thay vào đó. (~1\le x \le n,|y|\le10^9~)
  • Loại 2 có dạng ~2~ ~l~ ~r~: In ra độ ngon lớn nhất của các gói mì từ vị trí ~l~ đến ~r~ (~1\le l\le r\le n~)

Với mỗi truy vấn loại 2, hãy in ra câu trả lời trên một dòng.

Input

  • Dòng đầu tiên là số ~n~ là số các gói mì (~1\le n\le10^5~)
  • Dòng 2 là ~n~ số nguyên là độ ngon của các gói mì (~|a_i|\le10^9~)
  • Dòng 3 là 1 số ~q~ là số truy vấn(~1\le q \le10^5~)
  • ~q~ dòng sau, mỗi dòng là một truy vấn thuộc một trong hai loại trên.

Output

Với mỗi truy vấn loại 2, in ra câu trả lời trên một dòng

Sample Input

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

Sample Output

4
5
5
3

Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Bạn được cho một mảng gồm ~n~ số nguyên. Ban đầu tất cả các số của mảng đều là 0. Nhiệm vụ của bạn là xử lí 2 loại truy vấn:

  • Loại 1 có dạng ~1~ ~x~ ~y~: Gán phần tử ở vị trí thứ ~x~ trong dãy thành số ~y~ (~1\le x\le n,|y|\le 10^9~)
  • Loại 2 có dạng ~2~ ~l~ ~r~: In ra tổng các phần tử trong đoạn từ ~l~ đến ~r~ (~1\le l\le r\le n~)

Với mỗi truy vấn loại 2, hãy in ra câu trả lời trên một dòng.

Input

  • Dòng đầu tiên là hai số ~n~ và ~q~ lần lượt là số phần tử của mảng (~1\le n\le 10^5~) và số truy vấn (~1 \le q \le 10^5~).
  • ~q~ dòng sau, mỗi dòng là một truy vấn thuộc một trong 2 loại trên.

Output

Với mỗi truy vấn loại 2, in ra câu trả lời trên một dòng

Sample Input

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

Sample Output

7
11
10

Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Bạn được cho một mảng gồm ~n~ số nguyên. Nhiệm vụ của bạn là xử lí 2 loại truy vấn:

  • Loại 1 có dạng ~1~ ~x~ ~y~ ~val~: Tăng giá trị của các phần tử từ vị trí thứ ~x~ đến vị trí thứ ~y~ trong dãy lên ~val~ đơn vị (~1\le x \le y \le n,1\le val\le10^9~)
  • Loại 2 có dạng ~2~ ~l~ ~r~: In ra phần tử lớn nhất của dãy từ phần tử thứ ~l~ đến phần tử thứ ~r~ (~1\le l\le r\le n~)

Với mỗi truy vấn loại 2, hãy in ra câu trả lời trên một dòng.

Input

  • Dòng đầu tiên là số ~n~ là số phần tử của mảng (~1\le n\le10^5~)
  • Dòng 2 là ~n~ số nguyên là các phần tử của mảng ~a~ (~|a_i|\le10^9~)
  • Dòng 3 là 1 số ~q~ là số truy vấn(~1\le q \le10^5~)
  • ~q~ dòng sau, mỗi dòng là một truy vấn thuộc một trong hai loại trên.

Output

Với mỗi truy vấn loại 2, in ra câu trả lời trên một dòng

Sample Input

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

Sample Output

8
7
9

Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Trò chơi này thật đơn giản: Bạn có ~n~ hộp được đánh số từ 1 đến ~n~ và một số ~k~. Trong mỗi hộp có một tấm séc ghi số ~a_i~. Nếu bạn chọn hộp ~i~ và ~a_i\ge0~ thì bạn sẽ nhận được ~a_i~ đồng còn ~a_i \le 0~ thì bạn sẽ phải "lộp" cho chương trình ~|a_i|~ đồng.

Bằng khả năng "see the future" khủng của mình, bạn đã biết được con số ghi trên tấm séc trong mỗi hộp. Nhiệm vụ của bạn bây giờ chỉ còn là kiếm nhiều tiền nhất. Nhưng, trò chơi này có 2 điều luật như sau:

  • Ví dụ bạn chọn hộp thứ ~i~, thì hộp tiếp theo bạn chọn phải có chỉ số ~\le i+k~. Với hộp đầu tiên thì bạn có thể chọn tùy ý.
  • Bạn chỉ được chọn các hộp từ trái qua phải. Nói cách khác, nếu bạn chọn hộp thứ ~i~ thì hộp tiếp theo bạn chọn phải có số thứ tự ~>i~.

Bạn hãy tìm cách chơi để đem về nhà được nhiều tiền nhất nhé.

Input

  • Dòng đầu tiên là 2 số ~n~ và ~k~ (~1\le n,k \le 10^5~)
  • Dòng thứ 2 là ~n~ số nguyên là số ghi trên tấm séc trong mỗi hộp (~|a_i|\le 10^9~)

Output

1 số duy nhất là số tiền nhiều nhất bạn có thể kiếm được

Sample Input

5 2
-1 -2 3 -4 5

Sample Output

8

Giới hạn thời gian: 3.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài


Giới hạn thời gian: 6.0s / Giới hạn bộ nhớ: 768M

Điểm: 100

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài


Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài


Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài


Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài


Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài


Giới hạn thời gian: 2.0s / Giới hạn bộ nhớ: 256M

Điểm: 100

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài