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 BAI1.INP

• 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~).

Output BAI1.OUT

In ra 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, in ~-1~.

Scoring

Sample Input 1

5
2 3 4 5 1

Sample Output 1

7

Notes

Chọn dãy ~\{2, 4, 1\}~ (các phần tử ở vị trí 1, 3 và 5) có tổng 7 là số 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.

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 BAI2.INP

• 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 và 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 BAI2.OUT

In ra 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

Ba khu đất lần lượt là:

• Khu 1: ~(0, 0) \to (3, 2)~;
• Khu 2: ~(1, 1) \to (4, 3)~;
• Khu 3: ~(2, 0) \to (5, 4)~.

[Minh họa ba khu đất trong ví dụ]

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.

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\} \to \{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 BAI3.INP

• 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 BAI3.OUT

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.

Khách sạn X chuẩn bị bữa tiệc tối nay với một bàn tròn lớn gồm ~n~ ghế đánh số từ 1 đến ~n~ theo chiều kim đồng hồ: ghế thứ ~i~ (~\forall i = 1, \dots, n - 1~) kề với ghế thứ ~i + 1~ và ghế thứ ~n~ kề với ghế thứ 1.

Để đảm bảo tính thẩm mỹ, các ghế sẽ được phủ bằng khăn phủ ghế làm bằng vải thượng hạng, mỗi khăn phủ ghế được nhuộm một loại màu duy nhất. Khách sạn có tổng cộng ~k~ loại màu khăn được đánh số từ 1 đến ~k~, mỗi loại có số lượng vô hạn.

Trước giờ khai tiệc, đã có ~m~ (~m \le n~) chiếc ghế được phủ khăn, ghế thứ ~p_j~ (~\forall j = 1, \dots, m~) được phủ khăn màu ~c_j~. Các ghế còn lại chưa được phủ khăn và Quản lý có thể tự do chọn màu khăn phủ cho chúng sao cho thỏa mãn: toàn bộ ~n~ ghế đều phải được phủ khăn và không có hai ghế kề nhau nào được phủ màu giống nhau.

Hãy đếm số cách mà Quản lý có thể chọn phủ khăn sao cho thỏa mãn điều kiện trên. Hai cách được coi là khác nhau nếu tồn tại một chiếc ghế được phủ màu khác nhau trong hai cách đó. Do số cách có thể rất lớn nên hãy in ra kết quả sau khi chia lấy dư cho ~10^9 + 7~.

Trong bài này, bạn cần trả lời ~T~ truy vấn như trên.

Input BAI4.INP

• Dòng đầu chứa số nguyên ~T~ (~1 \le T \le 10^5~) là số truy vấn cần trả lời.
• Tiếp theo là ~T~ truy vấn, truy vấn thứ ~i~ gồm:
  • Dòng đầu truy vấn chứa ba số nguyên ~n~, ~k~, ~m~ (~3 \le n \le 10^{18}~; ~1 \le k \le 10^9~; ~0 \le m \le n~);
  • Tiếp theo là ~m~ dòng, mỗi dòng chứa hai số nguyên ~p_j~, ~c_j~ (~1 \le p_j \le n~; ~1 \le c_j \le k~).

Các ~p_j~ trong cùng một truy vấn đôi một khác nhau và được cho theo thứ tự bất kì. Dữ liệu bảo đảm tổng của các ~m~ trên toàn bộ ~T~ truy vấn không vượt quá ~2 \cdot 10^5~.

Output BAI4.OUT

Gồm ~T~ dòng, dòng thứ ~i~ (~1 \le i \le T~) là câu trả lời cho truy vấn thứ ~i~ (chia lấy dư cho ~10^9 + 7~).

Scoring

Sample Input 1

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

Sample Output 1

30
9
1

Notes

• Truy vấn 1: tổng cộng 30 cách phủ khăn thỏa mãn.
• Truy vấn 2: tổng cộng 9 cách phủ khăn thỏa mãn.
• Truy vấn 3: chỉ có hai cách phủ khăn để không có hai ghế liền kề cùng màu. Trong đó chỉ có một cách mà ghế 1 được phủ khăn màu 1.

Một nông trại có ~n~ khu vườn nối với nhau bởi ~n - 1~ con đường, mỗi con đường nối giữa hai khu vườn với nhau tạo thành dạng một cây đô thị. Khi thu hoạch người ta chọn khu vườn 1 làm gốc của cây đô thị. Khu vườn ~i~ đang có ~a_i~ thùng hoa quả. Ta quy ước nhánh của khu ~u~ bao gồm khu vườn ~u~ và mọi khu vườn nằm trong cây con nhận ~u~ làm gốc.

Trong ngày, diễn ra ~q~ sự kiện thuộc hai loại:

• ~1~ ~u~ ~x~: Toàn bộ các khu vườn thuộc nhánh khu ~u~, mỗi khu thu hoạch thêm ~x~ thùng hoa quả;
• ~2~ ~u~: Tính tổng số thùng hoa quả có trong toàn bộ các khu vườn thuộc nhánh của khu ~u~.

Hãy in ra câu trả lời cho các sự kiện loại 2 theo đúng thứ tự dữ liệu đầu vào.

Input BAI5.INP

• Dòng 1: chứa hai số nguyên ~n~, ~q~ (~1 \le n, q \le 2 \cdot 10^5~) lần lượt là số khu vườn và số sự kiện diễn ra trong ngày;
• Dòng 2: chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~0 \le a_i \le 10^9~, ~1 \le i \le n~);
• Tiếp theo là ~n - 1~ dòng, mỗi dòng chứa hai số nguyên ~u~, ~v~ mô tả một con đường (~1 \le u, v \le n~; ~u \ne v~). Các con đường được cho theo thứ tự bất kì và không bảo đảm ~u~ là cha của ~v~. Dữ liệu bảo đảm ~n - 1~ con đường này tạo thành một cây đô thị;
• Cuối cùng là ~q~ dòng, mỗi dòng mô tả một sự kiện thuộc một trong hai loại theo mô tả đề bài (~1 \le u \le n~; ~1 \le x \le 10^4~).

Output BAI5.OUT

Gồm nhiều dòng, mỗi dòng là một số nguyên tương ứng câu trả lời cho sự kiện loại 2 theo thứ tự dữ liệu đầu vào.

Scoring

Sample Input 1

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

Sample Output 1

11
41
45
14

Notes

Nhánh của khu vườn 2 gồm ~\{2, 4, 5\}~ với tổng số thùng là ~2 + 4 + 5 = 11~.

Sự kiện tiếp theo cộng 10 thùng cho cả ba khu này nên tổng số thùng của nhánh trở thành ~12 + 14 + 15 = 41~.

Toàn nông trại khi đó có 45 thùng và riêng khu 4 có 14 thùng.

Bạn đang chơi trò chơi Chiến dịch tập kích với bản đồ gồm ~N~ thành phố (đánh số từ 1 đến ~N~) được nối bởi ~M~ con đường một chiều. Để đi hết con đường thứ ~i~ tốn ~w_i~ đơn vị thời gian. Bạn xuất phát ở thành phố 1 tại thời điểm 0 và cần phá huỷ mục tiêu được đặt ở thành phố ~N~.

Có một số thành phố được bảo vệ bởi lá chắn phòng thủ. Lá chắn phòng thủ của một thành phố được duy trì bởi một số trạm phát đặt tại những thành phố khác. Muốn tiến vào một thành phố có lá chắn phòng thủ, trước hết phải phá huỷ toàn bộ các trạm phát duy trì lá chắn đó; mà muốn phá một trạm phát thì phải tiến được vào thành phố chứa trạm phát ấy.

Bạn có vô số robot cảm tử. Mỗi khi tiến vào một thành phố, một robot lập tức phá hủy một mục tiêu tại đó (phá hủy một trạm phát hoặc mục tiêu ở thành phố ~N~). Việc phá hủy không tốn thời gian; chỉ việc di chuyển trên các con đường mới tốn thời gian.

Hãy tính thời gian ít nhất để phá hủy được mục tiêu ở thành phố ~N~.

Input BAI6.INP

• Dòng đầu: gồm hai số nguyên ~N~ và ~M~ (~1 \le N \le 10^5~; ~1 \le M \le 3 \cdot 10^5~).
• ~M~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~u_i~, ~v_i~, ~w_i~ (~1 \le w_i \le 10^8~) mô tả một con đường một chiều từ thành phố ~u_i~ tới thành phố ~v_i~ tốn ~w_i~ đơn vị thời gian.
• ~N~ dòng tiếp theo, dòng thứ ~v~ mô tả thành phố ~v~: bắt đầu bằng số nguyên ~l_v~ là số trạm phát duy trì lá chắn của thành phố ~v~, tiếp theo là ~l_v~ số hiệu thành phố cho biết vị trí đặt mỗi trạm phát. Nếu ~l_v = 0~ thì thành phố ~v~ không có lá chắn (thành phố 1 bảo đảm không có lá chắn, tức ~l_1 = 0~).

Dữ liệu bảo đảm luôn có phương án phá hủy mục tiêu và không có trạm phát duy trì lá chắn của một thành phố nào lại nằm trong chính thành phố đó. Có thể có nhiều con đường nối cùng một cặp thành phố và có thể có đường đi từ một thành phố tới chính nó.

Output BAI6.OUT

Một số nguyên duy nhất là thời gian ít nhất để phá huỷ được mục tiêu ở thành phố ~N~.

Scoring

Sample Input 1

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

Sample Output 1

5

Notes

Thành phố 4 có lá chắn do trạm phát ở thành phố 5 duy trì.

Thành phố 6 có lá chắn do hai trạm phát ở thành phố 3 và 5 duy trì.

Phương án tối ưu tiến vào các thành phố theo thứ tự lần lượt là: ~2 \to 3 \to 5 \to 4 \to 6~.

Đáp án là 5.