Một dãy số gồm \(M\) phần tử \(a_1, a_2, ..., a_M\) được gọi là dãy số hai phía nếu thoả mãn điều kiện sau:

• \(M\) chẵn, khi đó chia dãy thành hai phần \(\{a_1, a_2, ..., a_{\frac{M}{2}}\}\) và \(\{a_{\frac{M}{2}+1}, ..., a_M\}\);
• Các phần tử ở mỗi phần có giá trị bằng nhau. Tức là \(a_1=a_2=...=a_{\frac{M}{2}}\) và \(a_{\frac{M}{2}+1}=...=a_M\);
• Giá trị của hai phần phải khác nhau. Tức là \(a_1 \neq a_M\).

Ví dụ:

• Dãy số hai phía: \(\{0, 0, 0, 1, 1, 1\}, \{1, 1, 2, 2\}, \dots\)
• Không phải dãy hai phía: \(\{1, 1, 0\}, \{0, 0, 2, 1\}, \{2, 2\}, \dots\)

Cho dãy số gồm \(N\) phần tử, mỗi phần tử nhận một trong ba giá trị \(0, 1, 2\) và số nguyên dương \(K\).

Hãy thay đổi không quá \(K\) phần tử của dãy để được dãy con dài nhất là dãy số hai phía.

Dữ liệu vào từ tệp văn bản DSHP.INP:

• Dòng đầu tiên chứa hai số nguyên \(N, K\) \((1\le K\le N\le 10^5)\);
• Dòng tiếp theo chứa \(N\) số \(0\) hoặc \(1\) hoặc \(2\) mô tả dãy số ban đầu.

Kết quả ghi ra tệp văn bản DSHP.OUT:

Một số nguyên duy nhất là độ dài lớn nhất của dãy số hai phía tìm được, sau khi thay đổi không quá \(K\) số của dãy số đã cho.

Ví dụ

Input

7 3
2 1 2 0 0 2 1

Output

6

Giải thích

Có thể thay đổi thành dãy số: \(\color{red}{2, \underline{2}, 2, 0, 0, \underline{0}}\)\(, 1\)

Hoặc cũng có thể thay đổi thành dãy số: \(\color{red}{\underline{1}, 1, \underline{1}, 0, 0, \underline{0}}\)\(, 1\)

Input

4 2
1 1 0 0

Output

4

Giải thích

Không cần thay đổi phần tử nào trong dãy số.

Ràng buộc

• Có \(50\%\) số test ứng với \(50\%\) số điểm thoả mãn: \(1\le K\le N\le 10^2\);
• \(30\%\) số test khác ứng với \(30\%\) số điểm thoả mãn: \(1\le K\le N\le 10^3\);
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

Cho xâu \(S\) gồm các chữ cái tiếng Anh in thường. Gọi \(f(S)\) là số lượng kí tự phân biệt của xâu \(S\). Ví dụ \(S =\) abccaaa, vậy \(f(S)=3\).

Với mỗi \(K\) có giá trị từ \(1\) đến \(f(S)\), hãy đếm số lượng xâu con \(X\) của \(S\) có \(f(X) = K\).

Dữ liệu vào:

Gồm một xâu \(S\) (có số lượng kí tự - kí hiệu là \(|S|\) không vượt quá \(10^6\)).

Kết quả ghi:

Gồm \(f(S)\) dòng, mỗi dòng là kết quả tương ứng khi \(K\) có giá trị từ \(1\) đến \(f(S)\).

Ví dụ

Input

abba

Output

5
5

Giải thích

Các xâu con có \(1\) kí tự phân biệt là (xâu được gạch chân): \(\underline{a} \textit{bba}, \textit{a}\underline{b}\textit{ba}, \textit{ab}\underline{b}\textit{a}, \textit{abb}\underline{a}, \textit{a}\underline{bb}\textit{a}\)

Các xâu con có \(2\) kí tự phân biệt là (xâu được gạch chân): \(\underline{ab}\textit{ba}, \underline{abb}\textit{a}, \underline{abba}, \textit{a}\underline{bba}, \textit{ab}\underline{ba}\)

Ràng buộc

• Có \(40\%\) số test ứng với \(40\%\) số điểm thoả mãn: \(|S|\le 10^2\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thoả mãn: \(|S|\le 2\times 10^3\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thoả mãn: \(|S|\le 10^5\);
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

Cho dãy số gồm \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\). Thao tác gộp dãy số lại như sau: chọn hai phần tử liên tiếp \(a_i\) và \(a_{i+1}\) có cùng giá trị là \(x\), rồi xoá \(a_{i+1}\) khỏi dãy và tăng \(a_i\) lên \(1\) thành \(x+1\), sau đó các phần tử còn lại của dãy được gộp lại.

Hãy tìm cách thực hiện liên tục các thao tác như trên để được dãy có ít phần tử nhất.

Dữ liệu vào từ tệp văn bản GDS.INP:

• Dòng đầu tiên chứa số nguyên dương \(N \ (1\le N\le 10^6)\);
• Dòng thứ hai chứa \(N\) số nguyên \(a_i\) \((1\le a_i\le 10^9; \ 1\le i\le N)\).

Kết quả ghi ra tệp văn bản GDS.OUT:

Ghi ra số lượng phần tử ít nhất có thể của dãy sau khi thực hiện liên tục các thao tác như trên để được dãy có ít phần tử nhất.

Ví dụ

Input

4
3 2 2 2

Output

2

Giải thích

Các bước gộp dãy số như sau:

• Dãy ban đầu: \(3 \ \underline{2} \ \underline{2} \ 2\)
• Gộp hai số ở vị trí \(2\) và \(3\) thì dãy số là: \(\underline{3} \ \underline{3} \ 2\)
• Gộp hai số ở vị trí \(1\) và \(2\) thì dãy số là: \(4 \ 2\)

Ràng buộc

• Có \(20\%\) số test ứng với \(20\%\) số điểm thoả mãn: \(N\le 10; \ a_i\le 30\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thoả mãn: \(N\le 200; \ a_i\le 30\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm thoả mãn: \(N\le 2000; \ a_i\le 30\);
• \(10\%\) số test khác ứng với \(10\%\) số điểm thoả mãn: \(N\le 2000\);
• \(10\%\) số test khác ứng với \(10\%\) số điểm thoả mãn: \(a_i\le 30\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm không có ràng buộc gì thêm.

Cho một cây gồm \(N\) đỉnh được đánh số từ \(1\) đến \(N\), trong đó đỉnh \(1\) là gốc của cây. Tất cả đỉnh trên đường đi từ đỉnh \(1\) đến đỉnh \(u\) được gọi là tổ tiên của đỉnh \(u\). Mỗi đỉnh đều có hai loại trọng số, đỉnh thứ \(i\) có trọng số đỉnh là \(a_i\) và trọng số tổ tiên là \(b_i\).

Tổ tiên chung gần nhất của một tập đỉnh là đỉnh chung đầu tiên của các đỉnh khi đi về đỉnh gốc \(1\) (nếu tập hợp gồm \(1\) đỉnh thì tổ tiên chung gần nhất là chính đỉnh đó). Ví dụ, như hình dưới, tổ tiên chung gần nhất của tập hợp đỉnh \(\{3, 7\}\) là đỉnh \(2\); tổ tiên chung gần nhất của tập hợp đỉnh \(\{4, 7, 1\}\) là đỉnh \(1\).

Xét một tập hợp gồm \(k \ (0 \lt k \le N)\) đỉnh phân biệt bất kì \(\{u_1, u_2, \dots, u_k\}\). Gọi \(p\) là tổ tiên chung gần nhất của \(k\) đỉnh. Khi đó giá trị của tập đỉnh này được tính bằng công thức: \(a_{u_1} \times a_{u_2} \times \dots \times a_{u_k} \times b_p\). Vậy một cây \(N\) đỉnh sẽ có \(2^N - 1\) tập đỉnh phân biệt.

Hãy tính tổng giá trị của tất cả các tập đỉnh có thể tạo ra.

Dữ liệu vào từ tệp văn bản TSTD.INP:

• Dòng đầu tiên chứa số nguyên dương \(N \ (N \le 10^6)\) là số đỉnh của cây;
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N \ (a_i \le 10^9; \ 1\le i\le N)\) mô tả trọng số đỉnh của các đỉnh tương ứng từ đỉnh \(1\) đến đỉnh \(N\);
• Dòng thứ ba chứa \(N\) số nguyên dương \(b_1, b_2, \dots, b_N \ (b_i \le 10^9; \ 1\le i\le N)\) mô tả trọng số khi nó là tổ tiên của các đỉnh tương ứng từ đỉnh \(1\) đến đỉnh \(N\);
• \(N - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v \ (u, v\le N)\) mô tả cạnh của cây.

Kết quả ghi ra tệp văn bản TSTD.OUT:

Gồm một số nguyên duy nhất là kết quả của bài toán, vì kết quả có thể rất lớn nên in ra phần dư của kết quả khi chia cho \(10^9+7\).

Ví dụ

Input

3
1 1 2
2 1 2
1 2
1 3

Output

21

Giải thích

• Tập đỉnh \(\{1\}\) có giá trị: \(2\)
• Tập đỉnh \(\{2\}\) có giá trị: \(1\)
• Tập đỉnh \(\{3\}\) có giá trị: \(4\)
• Tập đỉnh \(\{1, 2\}\) có giá trị: \(2\)
• Tập đỉnh \(\{1, 3\}\) có giá trị: \(4\)
• Tập đỉnh \(\{2, 3\}\) có giá trị: \(4\)
• Tập đỉnh \(\{1, 2, 3\}\) có giá trị: \(4\)

\(\Rightarrow\) Tổng là: \(21\)

Ràng buộc

• Có \(20\%\) số test ứng với \(20\%\) số điểm có \(N \le 15\) và cây có dạng đường thẳng: đỉnh \(1\) nối với đỉnh \(2\), đỉnh \(2\) nối với đỉnh \(3\), ..., đỉnh \(N-1\) nối với đỉnh \(N\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm có \(N\le 15\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm có cây có dạng đường thẳng: đỉnh \(1\) nối với đỉnh \(2\), đỉnh \(2\) nối với đỉnh \(3\), ..., đỉnh \(N-1\) nối với đỉnh \(N\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm có mọi trọng số đỉnh của các đỉnh đều là \(1\);
• \(20\%\) số test khác ứng với \(20\%\) số điểm không có ràng buộc gì thêm.