Bạn đã biết về "xâu đối xứng" rồi đúng không? Vậy hôm nay chúng ta sẽ định nghĩa về "xâu bất đối xứng" nhé.

Bạn được cho một xâu \(s\) gồm toàn các chữ cái in thường. Trong một thao tác, bạn được phép hoán đổi vị trí của hai kí tự bất kì của xâu \(s\).

Một xâu \(s\) độ dài \(n\) được gọi là "xâu bất đối xứng" khi với mọi \(i\) \((1 \le i \le n)\), \(s_{i} \neq s_{n - i + 1}\). Ví dụ, xâu string, dukkichi là "xâu bất đối xứng", nhưng xâu abacaba, aba, abcbd thì không phải.

Xác định số thao tác nhỏ nhất cần thực hiện để biến xâu \(s\) thành một "xâu bất đối xứng", nếu không làm được đưa ra -1.

Input

• Dòng thứ nhất chứa một số nguyên dương \(n\) \((1 \le n \le 2 \times 10^{5})\) - độ dài xâu \(s\).
• Dòng thứ hai chứa xâu \(s\) độ dài \(n\) chỉ chứa các ký tự latin in thường.

Output

• Đưa ra một dòng là một số nguyên duy nhất thỏa mãn điều kiện đề bài, nếu không làm được đưa ra -1.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 10^{3}\).
• Subtask \(2\) (\(30\%\) số điểm): xâu \(s\) chỉ gồm hai loại kí tự.
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

6
string

0

Thuận là một bác tiêu phu lừng danh về tài năng chặt cây của mình. Hôm nay Thuận sẽ trồng và chặt một hàng cây gồm \(n\) cây để lấy gỗ xây nhà mới cho mình, các cây được đánh số từ \(1\) đến \(n\) từ trái qua phải. Ở vị trí thứ \(i\), Thuận chỉ được phép trồng cây có độ cao không quá \(h_{i}\).

Thuận muốn tìm một loại cây có độ cao là số nguyên \(k\) \((k \leq h_{1}, k \leq h_{n})\) và trồng vào một số vị trí thích hợp, biết rằng cậu chắc chắn sẽ trồng cây vào vị trí thứ \(1\) và thứ \(n\).

Nếu cây ở vị trí thứ \(i\) (\(i < n\)) bị đổ, nó sẽ làm các cây ở vị trí trong khoảng \([i + 1, min(n, i + k)]\) đổ theo.

Hãy giúp Thuận tính xem, độ cao \(k\) nhỏ nhất có thể là bao nhiêu, sao cho nếu Thuận chặt đổ cây ở vị trí thứ \(1\) thì cây ở vị trí thứ \(n\) cũng bị đổ theo.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) \((n \leq 10^{7})\).
• Dòng thứ hai chứa \(n\) số nguyên không âm \(h_{1}, h_{2}, \ldots, h_{n}\) \((0 \leq h_{i} \leq n)\).

Dữ liệu bảo đảm tồn tại một đáp án hợp lệ.

Output

• In ra một số nguyên dương là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 1000\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^{5}\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^{6}\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

10 
10 1 2 0 3 4 5 0 2 10

2

Nhân ngày sinh nhật, An muốn mời bạn bè đến dự tiệc tại nhà của cậu. Kế hoạch của cậu là mua một số lượng bánh ngọt để chia đều cho mọi người, nếu sau khi chia đều vẫn còn dư bánh thì cậu sẽ giữ lại chúng và ăn dần. An dự tính sẽ mời không quá \(N\) nguời bạn và mua không quá \(M\) chiếc bánh. Vì cậu rất thích bánh ngọt nên cậu muốn số lượng bánh dư không nhỏ hơn \(L\) để cậu có thể ăn thỏa thích, nhưng nếu ăn nhiều quá thì cậu sẽ tăng cân nên cậu muốn số lượng bánh dư không vượt quá \(R\). An muốn biết có bao nhiêu cách chọn số luợng người bạn có thể mời và số lượng bánh có thể mua sao cho thỏa mãn được mong muốn của cậu. Lưu ý, An phải mời ít nhất một người bạn và mua ít nhất một chiếc bánh, nếu số lượng bánh nhỏ hơn số lượng người bạn được mời thì những người đó sẽ không ăn bánh và An sẽ giữ lại hết số bánh và ăn dần (nhưng số lượng vẫn phải thỏa mãn điều kiện của cậu).

Input

• Gồm một dòng duy nhất chứa bốn số nguyên \(N, M, L\) và \(R\) \((1 \leq N, M \leq 10^{6}, \ 0 \leq L \leq R \leq N - 1)\).

Output

• In ra số lượng cách chọn thỏa mãn yêu cầu bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N, M \leq 1000\).
• Subtask \(2\) (\(20\%\) số điểm): \(R = 0\).
• Subtask \(3\) (\(20\%\) số điểm): \(R = N - 1\).
• Subtask \(4\) (\(40\%\) số điểm): không giới hạn gì thêm.

Example

5 5 2 4

7

10 6 0 4

51

Đất nước THT gồm \(n\) thành phố được đánh số từ \(1\) tới \(n\). Đất nước THT rất thích bóng đá, ở thành phố thứ \(i\) có số sân vận động là \(a_{i}\). Do một vài chính sách đặc biệt của Bộ Thể Thao mà số sân vận động của các thành phố là không quá \(m\). Các thành phố của THT cũng có \(n - 1\) con đường hai chiều để kết nối các thành phố lại. Con đường thứ \(i\) sẽ nối hai thành phố \(u_{i}\) và \(v_{i}\), đảm bảo rằng mọi cặp thành phố đều có lộ trình di chuyển tới nhau. Nói cách khác, như bao đất nước trong thế giới OI, THT có thể ví như một đồ thị dạng cây.

Bộ Xây Dựng đã tạo ra một phương pháp để đánh giá độ hiệu quả trong giao thông của một tổ hợp các thành phố:

• Giả sử ta có một tập thành phố \(u_{1}, u_{2}, \ldots, u_{k}\), độ hiệu quả trong giao thông của tập hợp thành phố này chính bằng đường đi ngắn nhất nếu có thể xuất phát tại một thành phố tùy ý và đi qua hết các thành phố trong tập. Đường đi ở THT được tính theo số con đường mà lộ trình này đi qua.

Để hiểu rõ hơn về cách tính độ hiệu quả, hãy nhìn vào hình vẽ trên:

• Giả sử tập thành phố là \([3, 4, 5]\), độ hiệu quả của tổ hợp này là \(5\), bởi ta sẽ đi theo lộ trình: \(3 \rightarrow 2 \rightarrow 1 \rightarrow 4 \rightarrow 1 \rightarrow 5\). Dễ thấy không có lộ trình nào có thể ngắn hơn.
• Giả sử tập thành phố là \([2,5]\), độ hiệu quả của tổ hợp này là \(2\) với lộ trình: \(2 \rightarrow 1 \rightarrow 5\).
• Đối với tập thành phố rỗng hoặc có số thành phố bằng \(1\), độ hiệu quả được đánh giá là bằng \(0\).

Vì là một người đam mê bóng đá, chủ tịch Thuận quyết định ăn mừng \(120\) năm sinh nhật của FIFA bằng việc tổ chức một mùa giải bóng đá bất tận, trải dài từ ngày \(1\) tới ngày \(m\) (hãy cố chấp nhận rằng thực sự có nhiều ngày như vậy). Vào ngày thứ \(x\) \((1 \leq x \leq m)\), các trận đấu bóng đá sẽ được tổ chức tại các thành phố có số sân vận động chia hết cho \(x\).

Như vậy, lưu lượng khách di chuyển sẽ là rất lớn, Chính Phủ giao cho bạn - Bộ Công Nghệ - đối với mỗi ngày, hãy đánh giá độ hiệu quả của tổ hợp thành phố được tổ chức bóng đá. Nói cách khác, đối với mỗi ngày thứ \(x\) \((1 \leq x \leq m)\), bạn sẽ phải đánh giá độ hiệu quả của tập thành phố \([u_{1}, u_{2}, \ldots, u_{k}]\) thỏa mãn \(x \mid a[u_{i}]\) \((\forall 1 \leq i \leq k)\).

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,m\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq m \leq 10^{5})\)
• Dòng thứ hai chứa \(n\) số nguyên dương, số thứ \(i\) là \(a_{i}\), miêu tả số sân vận động ở thành phố \(i\) \((1 \leq a_{i} \leq m)\).
• \(n - 1\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên dương \(u_{i}\) và \(v_{i}\) miêu tả con đường hai chiều nối từ thành phố \(u_{i}\) tới thành phố \(v_{i}\).

Output

• In ra \(m\) dòng, dòng thứ \(i\) là độ hiệu quả của tổ hợp thành phố được sử dụng trong ngày thứ \(i\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): Tất cả các con đường thứ \(i\) trong khoảng \([1, n - 1]\) có dạng \(u_{i} = i, v_{i} = i + 1\).
• Subtask \(2\) (\(10\%\) số điểm): \(n \leq 10, m = 1\).
• Subtask \(3\) (\(15\%\) số điểm): \(m = 1\)
• Subtask \(4\) (\(10\%\) số điểm): \(m = 2\)
• Subtask \(5\) (\(30\%\) số điểm): \(n \leq 5 \times 10^{4}, m \leq 10^{4}\)
• Subtask \(6\) (\(20\%\) số điểm): Không có giới hạn gì thêm.

Example

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

5

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

7
4
2
0
0