Cho dãy ~a~ gồm ~n~ phần tử nguyên dương. Hãy đếm số tổng khác nhau có thể tạo ra từ các dãy con không nhất thiết liên tiếp của ~a~ (không tính dãy rỗng).

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả số phần tử trong dãy.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~.

Output

• Gồm một số nguyên dương miêu tả kết quả bài toán.

Constraints

• ~1 \le n \le 1000~
• ~0 < a_i \le 1000~.

Subtasks

• Subtask ~1~: ~n \le 20~ ~(30\%)~
• Subtask ~2~: ~n \le 50~ ~(40\%)~
• Subtask ~3~: Không có ràng buộc gì thêm ~(30\%)~

Sample Input 1:

3
1 4 5

Sample Output 1:

6

Sample Input 2:

4
1 1 1 1 

Sample Output 2:

4

Cho đồ thị vô hướng có trọng số gồm ~n~ đỉnh, đồng thời có thêm ~m~ truy vấn có một trong hai dạng như sau:

• ~1~ ~u~ ~v~ thêm cạnh ~(u,v)~ vào đồ thị.
• ~2~ ~u~ ~v~ in ra thời gian sớm nhất (chỉ số của truy vấn) để ~u~ và ~v~ liên thông.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5; 1 \le m \le 5*10^5)~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~t,u,v~, nếu ~t = 1~ thì là dạng truy vấn thứ nhất, ngược lại là dạng thứ hai.

Output:

• Với mỗi truy vấn loại ~2~, in ra kết quả. Nếu hai đỉnh chưa liên thông, in ra ~-1~.

Constraints:

• Có ~50\%~ số test ứng với ~n,m \le 2*10^3~;
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

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

Output

1
3
-1

Tỉ phú Vương dự định sẽ xây một thủy cung thu hút khách du lịch. Để thực hiện dự định đó, ông ta đã mua ~n~ chú cá và ~m~ bể thủy sinh. Chú cá thứ ~i~ có sức mạnh là ~a_i~

Vương cần phải quyết định xem, với mỗi chú cá thì ông sẽ đặt vào bể thủy sinh nào. Tuy nhiên, việc này không hề đơn giản, khi ông sẽ phải xem xét đến giới hạn không gian và khả năng kìm hãm sự phát triển lẫn nhau giữa những chú cá trong cùng một bể. Sau những tính toán kĩ lưỡng, ông đã ước tính rằng mức độ bất ổn của mỗi chú cá sẽ bằng tổng sức mạnh của các chú cá nằm cùng bể thủy sinh với chú cá đó (bao gồm cả bản thân chú cá đó).

Yêu cầu: Hãy giúp tỉ phú Vương đặt các chú cá vào các bể thủy sinh sao cho tổng độ bất ổn của các chú cá là nhỏ nhất.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ ~(1 \le m \le n \le 2000)~ cho biết số chú cá và số bể thủy sinh.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, . . . , a_n (1 \le ai \le 10^9 )~ cho biết sức mạnh của các chú cá.

Output

• In một số nguyên duy nhất là tổng độ bất ổn nhỏ nhất của các chú cá.

Subtask

• Có ~20\%~ số test ứng với ~n \le 8~.
• Có ~20\%~ số test khác ứng với ~n \le 15~.
• Có ~20\%~ số test khác ứng với ~m = 2~.
• Có ~30\%~ số test khác ứng với ~n \le 100~.
• ~10\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

6 3
9 2 11 3 5 8

Sample Output 1

75

Sample Input 2

4 4
10 20 30 40

Sample Output 2

100

Explanation

Trong ví dụ thứ nhất, một cách đặt cá vào bể thủy sinh tối ưu như sau:

• Đặt chú cá thứ ~1, 6~ vào bể thứ nhất.
• Đặt chú cá thứ ~2, 4, 5~ vào bể thứ hai.
• Đặt riêng chú cá thứ ~3~ vào bể thứ ba. Độ bất ổn của các chú cá lần lượt là ~17 + 10 + 11 + 10 + 10 + 17 = 75~.

Ở ví dụ thứ hai, ta sẽ đặt riêng mỗi chú cá vào một bể thủy sinh.

Biểu thức ngoặc đúng được định nghĩa như sau:

• Một xâu rỗng biểu diễn một biểu thức ngoặc đúng;
• Nếu ~A~ là một xâu biểu diễn một biểu thức ngoặc đúng thì ~(A)~ cũng là biểu diễn một biểu thức ngoặc đúng;
• Nếu hai xâu ~A,B~ là xâu biểu diễn biểu thức ngoặc đúng thì ~AB~ cũng là biểu diễn một biểu thức ngoặc đúng.

Thầy Alice muốn tạo một biểu thức ngoặc đúng, có ~n~ vị trí có thể đặt ngoặc. Các vị trí được đánh số từ ~1~ tới ~n~ từ trái sang phải, bắt đầu với giá trị ~s = 0~, tại mỗi vị trí ~(1 \le i\le n)~ thầy Alice có ba lựa chọn:

• Đặt vị trí này là dấu ~(~ và thay ~s = s + a_i~
• Đặt vị trí này là dấu ~)~ và thay ~s = s - a_i~
• Bỏ qua vị trí này.

Sau khi lựa chọn xong, lấy các kí tự từ trái sang phải ở các vị trí đặt dấu ~(~ hoặc ~)~ để tạo được biểu thức ngoặc đúng mà ~s~ đạt giá trị lớn nhất.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, . . . , a_n ( |a_i| \le 10^9 )~

Output

• In ra một số nguyên duy nhất là giá trị ~s~ lớn nhất có thể chọn được.

Subtask

• Có ~25\%~ số test ứng với ~n \le 10~.
• Có ~25\%~ số test khác ứng với ~n \le 10^3~.
• Có ~25\%~ số test khác ứng với ~n \le 10^5~ và không có quá ~10^3~ giá trị ~a_i~ khác ~0~.
• Có ~25\%~ số test khác ứng với ~n \le 10^5~.

Sample Input 1

4
0 -5 1 2

Sample Output 1

5

Sample Input 2

9
5 -2 2 3 -4 -4 -1 -2 9

Sample Output 2

21

Cho đồ thị vô hướng có trọng số gồm ~n~ đỉnh và ~m~ cạnh không chứa khuyên, mỗi cạnh có dạng ~(u,v,c)~, tức là cạnh nối hai đỉnh ~u~ và ~v~ có trọng số ~c~. Lưu ý, không tồn tại quá 5 cạnh có cùng trọng số là ~c~.

Hãy đếm số cây khung nhỏ nhất của đồ thị này. Nói cách khác, đếm số cách giữ lại ít cạnh nhất của đồ thị sao cho đồ thị vẫn liên thông và tổng trọng số các cạnh giữ lại là nhỏ nhất.

Do kết quả có thể rất lớn, hãy in ra đáp số theo modulo ~998244353~.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, n-1 \le m \le 2*10^5)~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~3~ số nguyên ~u_i,v_i,w_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 10^9)~ - lần lượt là hai đỉnh và trọng số của cạnh thứ ~i~.
• Dữ liệu đảm bảo đồ thị liên thông.

Output:

• Gồm một số nguyên duy nhất là số cây khung nhỏ nhất của đồ thị modulo ~998244353~.

Constraints:

• Có ~10\%~ số test ứng với ~m \le 7~
• Có ~20\%~ số test ứng với ~m \le 25~
• Có ~30\%~ số test ứng với ~n = m~;
• ~40\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input 1

3 3
1 2 1
2 3 1
3 1 1

Output 1

3

Input 2

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

Output 2

2

Input 3

4 9
1 2 1
1 2 1
2 3 2
2 3 2
2 3 2
3 4 3
3 4 3
3 4 3
3 4 3

Output 3

24