Bessie đang chơi một trò chơi điện tử, trong đó cô cần đánh bại một hàng gồm \(N\) kẻ địch có lượng HP ban đầu được cho bởi dãy \(v_1\dots v_N\) (\(1\le N\le 2\cdot 10^5\), \(0\le v_i\le 10^9\)). Trong một đòn tấn công, cô có thể thực hiện lần lượt các bước sau:

• Chọn \(i\) sao cho kẻ địch thứ \(i\) vẫn còn sống (tức là \(v_i>0\)).
• Gây một điểm sát thương cho kẻ địch thứ \(i\) và tất cả kẻ địch kề với nó mà vẫn còn sống. Cụ thể, với mỗi \(j\in[\max(i-1,1),\min(i+1,N)]\), nếu \(v_j>0\) thì trừ \(v_j\) đi một.

Hãy giúp Bessie xác định số đòn tấn công ít nhất cần dùng để đánh bại tất cả kẻ địch (tức là giảm mọi \(v_i\) về \(0\)).

Ngoài ra, bạn được cho một tham số \(M\) (\(0\le M\le 2\)). Nếu \(M>0\), hãy in ra một cách thực hiện đạt số đòn tấn công tối thiểu với số lượt tấn công liên tiếp nhỏ, trong đó một lượt là việc tấn công cùng một kẻ địch liên tiếp.

Gọi \(R\) là số lượt trong cách thực hiện của bạn. Cách thực hiện phải có định dạng sau: in \(R\) trên một dòng riêng, sau đó là \(R\) dòng, mỗi dòng chứa hai số nguyên \(i\) và \(r\) (\(1\le i\le N\), \(0\le r\le 10^9\)), có nghĩa là Bessie tấn công kẻ địch thứ \(i\) liên tiếp \(r\) lần.

Tùy theo giá trị của \(M\), \(R\) phải thỏa mãn một trong các ràng buộc sau:

• \(M=1\): \(R\le 2N\) (có thể chứng minh rằng một cách thực hiện như vậy luôn tồn tại).
• \(M=2\): \(R\le f(N)\), trong đó \(f(N)\) là giá trị lớn nhất, xét trên mọi dãy có độ dài \(N\), của số lượt tối thiểu.

Dữ liệu vào

Mỗi dữ liệu vào gồm \(T\) (\(1\le T\le 10^5\)) bộ kiểm thử độc lập. Dòng đầu tiên chứa \(T\) và \(M\).

Mỗi bộ kiểm thử được mô tả như sau:

Dòng đầu tiên chứa \(N\).

Dòng thứ hai chứa \(v_1\dots v_N\).

Đảm bảo rằng tổng \(N\) trên tất cả các bộ kiểm thử không vượt quá \(10^6\).

Dữ liệu ra

Với mỗi bộ kiểm thử, ở dòng đầu tiên, in số đòn tấn công tối thiểu.

Sau đó, nếu \(M>0\), in thêm \(R+1\) dòng như mô tả ở trên. Mọi cách thực hiện hợp lệ đều được chấp nhận.

Ví dụ

2 0
1
10
3
6 1 7

10
12

2 1
1
10
3
6 1 7

10
2
1 0
1 10
12
4
2 1
1 5
3 2
3 4

2 2
1
10
3
6 1 7

10
1
1 10
12
3
2 1
3 6
1 5

Phân nhóm

• Dữ liệu 4–7: \(M=0\).
• Dữ liệu 8–11: \(M=1\).
• Dữ liệu 12–13: \(M=2\).

Nguồn

USACO 2026 Contest 3, Platinum — “Blast Damage” — tác giả: Benjamin Qi.
https://usaco.org/index.php?page=viewproblem2&cpid=1597