Sau khi học sinh đã đăng kí danh sách tham gia trại hè, nhà trường cần đặt phòng khách sạn theo nhu cầu của học sinh. Theo thông tin đăng kí nhận được thì có ~a~ học sinh muốn ở phòng riêng (một mình một phòng) và có ~b~ học sinh không có yêu cầu gì, tùy theo sắp xếp của nhà trường. Biết rằng mỗi phòng chỉ ở tối đa ~3~ học sinh.

Yêu cầu: Hãy tính số lượng phòng ít nhất mà nhà trường cần đặt.

INPUT

Hai số nguyên ~a~ và ~b~ (~0 \leq a, b \leq 10^9~).

OUTPUT

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

SAMPLE INPUT

1 4

SAMPLE OUTPUT

3

SUBTASKS

• ~70%~ test tương ứng với ~70%~ số điểm có ~0 \leq b \leq 10^6~.
• ~30%~ test tương ứng với ~30%~ số điểm còn lại không có ràng buộc gì thêm.

Trong hội trại năm nay, Tí được lớp giao nhiệm vụ tham gia trò chơi giải mật thư tìm kho báu. Mật thư có ~n~ kí tự chỉ gồm hai loại kí tự là A và B. Trong mật thư, nếu số lần chuỗi con AA xuất hiện nhiều hơn số lần xuất hiện của chuỗi con BB thì đáp án của mật thư là số lần xuất hiện chuỗi con AA và ngược lại.

Tí vô tình làm ướt mật thư nên một số kí tự có thể bị nhòe mực, lúc này kí tự nhòe bị thay thế bởi kí tự *.

Yêu cầu: Hãy giúp Tí tìm ra một số lớn nhất có thể là đáp án của mật thư nếu nó không bị ướt.

INPUT

• Dòng đầu tiên chứa số nguyên dương ~n~ là độ dài của mật thư (~1 \leq n \leq 10^6~).
• Dòng thứ hai chứa n kí tự A, B hoặc * được ghi liền tiếp không chứa dấu cách.

OUTPUT

Chỉ gồm một số nguyên duy nhất là đáp án của bài toán.

SAMPLE INPUT 1

5
AABBB

SAMPLE OUTPUT 1

2

Giải thích:

• Chuỗi AA xuất hiện ~1~ lần. Chuỗi BB xuất hiện ~2~ lần. Vậy đáp án bài toán là ~2~.

SAMPLE INPUT 2

4 
A*BB

SAMPLE OUTPUT 2

2

Giải thích:

• Nếu kí tự * là kí tự B thì chuỗi BB xuất hiện ~2~ lần, còn chuỗi AA không xuất hiện lần nào.
• Ngược lại nếu kí tự * là kí tự A thì chuỗi AA xuất hiện ~1~ lần và chuỗi BB cũng xuất hiện ~1~ lần. Vậy đáp án bài toán là ~2~.

SUBTASKS

• ~50\%~ test tương ứng ~50\%~ số điểm với mật thư chỉ gồm hai kí tự A và B.
• ~50\%~ test tương ứng ~50\%~ số điểm còn lại không có ràng buộc gì thêm.

Sở thích của Tí và Tèo là giải những bài toán liên quan tới dãy số. Lần này Tí ghi ra một dãy số gồm ~n~ số nguyên trên một dòng và một số nguyên dương ~k~ rồi yêu cầu Tèo tìm dãy con có đúng ~k~ phần tử liên tiếp thỏa mãn các yêu cầu sau:

1. Tổng các phần tử trong dãy con là lớn nhất.
2. Nếu có nhiều dãy con thỏa mãn yêu cầu (1) thì chọn dãy con có nhiều số chẵn nhất.
3. Nếu có nhiều dãy con thỏa mãn yêu cầu (2) thì chọn dãy con có chỉ số của phần tử đầu tiên nhỏ nhất.

Tèo loay hoay cả buổi mà vẫn chưa giải được.

Yêu cầu: Bạn hãy giúp Tèo giải bài toán trên.

INPUT

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1 \leq k \leq n \leq 10^6~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~|a_i| \leq 10^9~, ~1 \leq i \leq n~).

OUTPUT

Hai số nguyên trên cùng một dòng lần lượt là chỉ số của phần tử đầu tiên và chỉ số của phần tử cuối cùng trong dãy con tìm được.

SAMPLE INPUT

5 2 
2 -3 8 13 -20

SAMPLE OUTPUT

3 4

SUBTASKS

• ~50\%~ test tương ứng ~50\%~ số điểm có ~1 \leq k \leq n \leq 10^3~.
• ~50\%~ test tương ứng ~50\%~ số điểm không có ràng buộc gì thêm.

Số chính phương là số mà nếu lấy căn bậc hai của nó thì được một số nguyên dương. Hay nói cách khác, bình phương của một số nguyên dương là một số chính phương. Ví dụ: 9 là số chính phương vì ~\sqrt{9} = 3~ (hay ~3^2 = 9~), nên 9 là số chính phương. Nhưng 10 thì không phải số chính phương vì ~\sqrt{10} \approx 3,16228~.

Yêu cầu: Cho ~n~ số nguyên dương ~x_1, x_2, ..., x_n~. Tương ứng với mỗi ~x_i~ (~1 \leq i \leq n~), hãy cho biết có nhiều nhất bao nhiêu số chính phương khác nhau mà tổng của chúng không vượt quá ~x_i~.

INPUT

• Dòng đầu chứa số nguyên dương ~n~ (~1 \leq n \leq 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~x_1, x_2, ..., x_n~ (~1 \leq x_i \leq 10^{18}~, ~1 \leq i \leq n~).

OUTPUT

~n~ số nguyên trên cùng một dòng trong đó số thứ ~i~ là đáp án cần tìm tương ứng của ~x_i~.

SAMPLE INPUT

2
14 10

SAMPLE OUTPUT

3 2

Giải thích:

• Với ~x_1 = 14~ ta chỉ có thể chọn nhiều nhất ~3~ số chính phương là ~1, 4, 9~ vì ~1 + 4 + 9 \leq 14~.
• Với ~x_2 = 10~ ta chỉ có thể chọn nhiều nhất ~2~ số chính phương là ~1~ và ~4~ hoặc ~1~ và ~9~ vì ~1 + 4 \leq 10~ hoặc ~1 + 9 \leq 10~.

SUBTASKS

• ~50\%~ test tương ứng với ~50\%~ số điểm có ~1 \leq n \leq 10^3, 1 \leq x_i \leq 10^9~.
• ~50\%~ test tương ứng với ~50\%~ số điểm còn lại không có ràng buộc gì thêm.