Nikolay có một chuỗi s có độ dài bằng n, chỉ bao gồm các chữ cái Latinh viết thường 'a' và 'b'. Vị trí của nó được đánh số từ 1 đến n. Anh ta muốn sửa đổi chuỗi của mình sao cho mỗi tiền tố có độ dài chẵn của nó có số lượng chữ cái 'a' và 'b' bằng nhau. Để đạt được điều đó, Nikolay có thể thực hiện thao tác sau tùy ý số lần (có thể là cần thực hiện thao tác nào):

Chọn một số vị trí trong chuỗi của mình và thay thế chữ cái trên vị trí này bằng chữ cái khác (nghĩa là thay 'a' bằng 'b' hoặc thay thế ' b 'với' a ').

Nikolay không thể sử dụng chữ cái nào ngoại trừ 'a' và 'b'. Tiền tố của chuỗi s có độ dài l (1≤l≤n) là một chuỗi s [1..l].

Ví dụ: đối với chuỗi s = "abba", có hai tiền tố có độ dài chẵn. Đầu tiên là s [1..2] = "ab" và s thứ hai [1...4] = "abba". Cả hai đều có cùng số 'a' và 'b'.

Nhiệm vụ của bạn là tính toán số lượng hoạt động tối thiểu Nikolay phải thực hiện với chuỗi s để sửa đổi nó để mỗi tiền tố có độ dài chẵn của nó có số lượng chữ cái 'a' và 'b' bằng nhau.

Đầu vào:

• Dòng đầu tiên của đầu vào chứa một số nguyên n chẵn (2≤n≤2⋅10^5) - độ dài của chuỗi s.
• Dòng thứ hai của đầu vào chứa chuỗi s có độ dài n, chỉ bao gồm các chữ cái Latinh viết thường 'a' và 'b'.

Đầu ra:

• Trong dòng đầu tiên, số lượng hoạt động tối thiểu Nikolay phải thực hiện với chuỗi s để sửa đổi nó để mỗi tiền tố có độ dài chẵn của nó có số lượng chữ cái 'a' và 'b' bằng nhau.
• Trong dòng thứ hai in chuỗi Nikolay có được sau khi áp dụng tất cả các thao tác. Nếu có nhiều câu trả lời, bạn có thể in bất kỳ câu trả lời nào.

Input:

4
bbbb

Output:

2
abab

Nhà An có N cái cây, cây thứ i có chiều cao ban đầu là A[i] cm. An vừa mua được M lọ thuốc tăng trưởng cực tốc. Mỗi lọ thuốc khi tưới vào một cái cây bất kỳ sẽ giúp cây đó cao thêm đúng 1 cm ngay lập tức (một cây có thể được tưới nhiều lọ thuốc).

An muốn sử dụng M lọ thuốc này một cách hợp lý nhất để chiều cao của cái cây thấp nhất trong vườn là cao nhất có thể.

Yêu cầu: Hãy tính chiều cao của cái cây thấp nhất sau khi An đã sử dụng tối ưu toàn bộ M lọ thuốc.

Dữ liệu vào: Đọc từ thiết bị chuẩn (bàn phím)

Dòng đầu tiên chứa hai số nguyên dương N và M (1 <= N <= 10^5, 0 <= M <= 10^9).

Dòng thứ hai chứa N số nguyên biểu diễn chiều cao ban đầu của các cây A[1], A[2], ..., A[N] (0 <= A[i] <= 10^9).

Dữ liệu ra: Ghi ra thiết bị chuẩn (màn hình)

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Input:

3 4 
2 4 6

Output:

5

Giải thích ví dụ:

Có 3 cây với chiều cao lần lượt là 2, 4, 6. An có 4 lọ thuốc.

Phương án tối ưu:

Dùng 3 lọ thuốc cho cây thứ nhất: Chiều cao từ 2 -> 5.

Dùng 1 lọ thuốc cho cây thứ hai: Chiều cao từ 4 -> 5.

Cây thứ ba không dùng thuốc: Chiều cao giữ nguyên là 6.

Sau khi dùng hết 4 lọ thuốc, chiều cao của các cây là: 5, 5, 6. Cái cây thấp nhất trong vườn lúc này cao 5cm. Đây là kết quả tối ưu nhất.

Nhập vào một mảng các số nguyên A có N phần tử và một số nguyên X, đếm xem X xuất hiện bao nhiêu lần trong mảng.

Ràng buộc: ~0 < N \leq 10^6~; ~-10^6 \leq A[i], X \leq 10^6~

Dữ liệu vào gồm 2 dòng, dòng thứ nhất là số lượng N phần tử và X, dòng thứ 2 lần lượt là N phần tử trong mảng A.

Input 01:

5 3
5 1 4 6 3

Output 01:

1

Số 3 xuất hiện 1 lần trong mảng

Input 02:

6 2
1 3 1 4 1 7

Output 02:

0

Tìm giá trị trung bình lớn nhất của một mảng con liên tiếp có độ dài ít nhất là K.

Input:

• Dòng 1: N, K (1 ≤ K ≤ N ≤ 10^5).

• Dòng 2: A; (1 ≤ Ai ≤ 10^9).

Output: In ra kết quả làm tròn xuống (số nguyên lớn nhất ≤ giá trị thực).

Input:

5 2
1 10 10 1 1

Output:

10

Đề bài: Cho số nguyên N và K. Hãy đếm số lượng ước của N mà không chia hết cho K.

Dữ liệu vào:

Dòng 1: Q (1 <= Q <= 10^5).

Mỗi dòng: N, K (1 <= N, K <= 10^6).

Dữ liệu ra:

Kết quả.

Ví dụ:

Input:

1 
12 2

Output:

2

Giải thích: Ước của 12 là 1, 2, 3, 4, 6, 12. Các ước không chia hết cho 2 là 1, 3.