Đội quân Pokémon

Cho dãy số nguyên đôi một phân biệt $a_1,a_2,\dots ,a_n$.

Với mọi dãy con (không nhất thiết liên tiếp, không rỗng) $a_{b_1},a_{b_2},\dots ,a_{b_k}$ với $1\le b_1<b_2<\dots <b_k\le n$, ta định nghĩa độ mạnh của dãy con đó là tổng đan dấu:

$$a_{b_1}-a_{b_2}+a_{b_3}-a_{b_4}+\dots$$

Bạn cần tìm độ mạnh lớn nhất có thể của một dãy con bất kỳ.

Sau đó có $q$ truy vấn. Mỗi truy vấn cho hai chỉ số $l$ và $r$ — hãy hoán đổi $a_l$ và $a_r$, rồi in lại độ mạnh lớn nhất.

Dữ liệu vào

Dòng đầu chứa số nguyên dương $t$ — số bộ test.

Với mỗi bộ test:

• Dòng đầu chứa hai số $n$ và $q$.
• Dòng thứ hai chứa $n$ số nguyên phân biệt $a_1,a_2,\dots ,a_n$ ($1\le a_i\le n$).
• $q$ dòng tiếp theo, mỗi dòng chứa hai số $l_i$ và $r_i$ ($1\le l_i\le r_i\le n$).

Dữ liệu ra

Với mỗi bộ test, in ra $q+1$ số nguyên: độ mạnh lớn nhất trước khi có thao tác hoán đổi, và sau mỗi thao tác hoán đổi.

Ràng buộc

• $1\le t\le {10}^3$
• $1\le n\le 3·{10}^5$
• $0\le q\le 3·{10}^5$
• $1\le a_i\le n$ và các $a_i$ đôi một phân biệt trong mỗi bộ test.
• Tổng $n$ trên tất cả bộ test không vượt quá $3·{10}^5$.
• Tổng $q$ trên tất cả bộ test không vượt quá $3·{10}^5$.

Ví dụ