Độ khó: Khá (3/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Cho một số nguyên dương ~n~ và dãy gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~. Một "dãy con không kề nhau" là dãy được tạo ra bằng cách chọn ra một số phần tử của dãy sao cho không có hai phần tử nào được chọn có vị trí ban đầu kề nhau.

Hãy chọn ra một dãy con không kề nhau sao cho thỏa mãn hai điều kiện sau:

• Tổng các phần tử được chọn là một số lẻ;
• Tổng các phần tử được chọn là lớn nhất có thể.

Input

• Dòng ~1~ chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~;
• Dòng ~2~ chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9, i = 1, 2, \dots, n)~.

Output

Một số nguyên là tổng lẻ lớn nhất tìm được. Nếu không tìm được dãy con thỏa mãn, xuất ~-1~.

Scoring

Sample Input 1

5
2 3 4 5 1

Sample Output 1

7

Notes

Chọn dãy ~\{2, 4, 1\}~ có tổng lẻ và không có hai phần tử được chọn nào kề nhau. Đây là dãy có tổng lớn nhất thỏa mãn.

Độ khó: Khó (4/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Phòng quy hoạch đô thị sử dụng hệ trục tọa độ Oxy để mô hình hóa phần đất quản lý. Hiện nay, phòng nhận được ~n~ tờ trình, tờ trình thứ ~i~ ~(1 \le i \le n)~ xin cấp một khu đất hình chữ nhật có các cạnh song song với các trục tọa độ, xác định bởi tọa độ góc trái dưới ~(x_1, y_1)~ và góc phải trên ~(x_2, y_2)~. Các khu đất có thể chồng lấn nhau tùy ý.

Một điểm trên mặt đất được gọi là điểm tranh chấp mức ~K~ nếu nó nằm trong ít nhất ~K~ khu đất được xin cấp phép. Lưu ý rằng điểm nằm trên biên của một khu đất cũng được tính là nằm trong khu đất đó.

Hãy tính tổng diện tích phần mặt đất gồm các điểm tranh chấp mức ~K~.

Input

• Dòng đầu chứa hai số nguyên ~n, K~ ~(1 \le n \le 10^5; 1 \le K \le 10)~ lần lượt là số lượng tờ trình, mức độ tranh chấp ~K~;
• Tiếp theo là ~n~ dòng, mỗi dòng mô tả một khu đất được xin cấp gồm bốn số nguyên ~x_1, y_1, x_2, y_2~ ~(0 \le x_1 < x_2 \le 10^9; 0 \le y_1 < y_2 \le 10^9)~.

Output

Một số nguyên duy nhất là diện tích cần tìm.

Scoring

Sample Input 1

3 2
0 0 3 2
1 1 4 3
2 0 5 4

Sample Output 1

6

Notes

Phần đất bị đúng hai khu phủ gồm ba mảnh có diện tích ~1, 1, 3~; phần bị cả ba khu phủ có diện tích ~1~ và cũng được tính. Tổng diện tích các điểm nằm trong ít nhất hai khu bằng ~6~.

Độ khó: Khó (4/4 điểm)

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn

Với một dãy ~b~ gồm các số nguyên dương, ta định nghĩa "chi phí nới" của ~b~ là số lần ít nhất phải thực hiện thao tác sau để dãy trở thành không giảm:

• Chọn một chỉ số ~i~ ~(1 \le i \le |b|~, với ~|b|~ là độ dài hiện tại của dãy), rồi thay phần tử ~b_i~ bằng hai số nguyên dương ~x~ và ~y~ thỏa mãn ~x + y = b_i~. Sau thao tác, độ dài dãy tăng thêm ~1~ và thao tác kế tiếp thực hiện trên dãy mới.

Chẳng hạn với dãy ~b = \{2, 4, 3\}~, chọn ~i = 2~ có thể biến dãy thành ~\{2, 1, 3, 3\}~ hoặc ~\{2, 2, 2, 3\}~ hoặc ~\{2, 3, 1, 3\}~; chỉ cần một thao tác ~\{2, 4, 3\} \rightarrow \{2, 2, 2, 3\}~ là dãy đã trở thành không giảm, nên chi phí nới của nó bằng ~1~. Có thể chứng minh mọi dãy số nguyên dương đều có thể làm cho không giảm theo cách này.

Cho dãy ~a~ gồm ~n~ số nguyên. Hãy tính tổng chi phí nới của tất cả các dãy con liên tiếp khác rỗng của ~a~, lấy theo mô-đun ~998244353~. Một dãy con liên tiếp là dãy thu được bằng cách bỏ đi một số phần tử ở đầu và ở cuối của dãy ban đầu; nếu một dãy con xuất hiện nhiều lần thì chi phí nới của nó được cộng đúng bằng số lần nó xuất hiện.

Input

• Dòng đầu chứa số nguyên ~t~ ~(1 \le t \le 10^4)~ là số truy vấn cần trả lời;
• Mỗi truy vấn gồm hai dòng:
  • Dòng đầu truy vấn chứa số nguyên ~n~ ~(1 \le n \le 10^5)~;
  • Dòng thứ hai của truy vấn chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^5)~.
• Dữ liệu bảo đảm tổng của các ~n~ trên tất cả các truy vấn không vượt quá ~10^5~.

Output

Với mỗi truy vấn, in ra trên một dòng tổng chi phí nới của mọi dãy con liên tiếp, lấy theo mô-đun ~998244353~.

Scoring

Sample Input 1

3
3
5 4 3
1
69
4
3 2 1 4

Sample Output 1

5
0
9

Notes

Truy vấn thứ nhất, dãy ~\{5, 4, 3\}~:

• Chi phí nới của ~\{5, 4, 3\}~ là ~3~, của ~\{5, 4\}~ là ~1~, của ~\{4, 3\}~ là ~1~, còn ba dãy một phần tử đều có chi phí nới là ~0~;
• Tổng chi phí nới là: ~3 + 1 + 1 + 0 + 0 + 0 = 5~.

Truy vấn thứ hai: chỉ có một phần tử nên tổng chi phí nới bằng ~0~.

Truy vấn thứ ba, tổng chi phí nới là ~9~.