Bạn được cung cấp một chuỗi s = s1 s2 …. sn có độ dài n, chỉ chứa các chữ số 1, 2, ..., 9. Một chuỗi con s [l...r] của s là một chuỗi liên tiếp bắt đầu từ vị trí l tới vị trí r ở trong chuỗi ban đầu. Một chuỗi con s[l … r] của s ngay cả khi nó là một chuỗi rỗng. Tìm số lượng các chuỗi con là số chẵn của s. Lưu ý rằng ngay cả khi một số chuỗi con giống nhau, nhưng có l và r khác nhau, chúng được tính là các chuỗi con khác nhau.

Đầu vào:

• Dòng đầu tiên chứa số nguyên n (1≤n≤65000) - độ dài của chuỗi s.
• Dòng thứ hai chứa một chuỗi s có độ dài n. Chuỗi s chỉ bao gồm các chữ số 1, 2, ..., 9.

Đầu ra: In số lượng các phần tử chẵn của s.

Input:

4
1234

Output:

6

Cho hai số nguyên a, b. Xét phân số a/b

• Nếu phân số trên không hợp lệ, in ra "INVALID"

• Nếu phân số trên là số nguyên, in ra số nguyên đó.

• Ngược lại, in ra dạng tối giản của phân số trên. Lưu ý mẫu phân số phải dương.

Input:

• Hai số nguyên a, b. (a, b ≤ 10^9)

Output:

• Kết quả bài toán

Input:

4 -8

Output:

-1 2

Bạn được cho một mảng gồm n số nguyên, và nhiệm vụ của bạn là tìm ba giá trị (tại ba vị trí khác nhau) sao cho tổng của chúng bằng x.

Input:

Dòng đầu tiên chứa hai số nguyên n và x — kích thước mảng và tổng cần tìm.

Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ — các giá trị trong mảng.

Output:

In ra ba số nguyên: chỉ số của ba phần tử tạo thành tổng x.

Nếu có nhiều đáp án, bạn có thể in ra bất kỳ một đáp án nào.

Nếu không có lời giải, in ra IMPOSSIBLE.

Ràng buộc:

~1 \le n \le 5000~

~1 \le x,a_i \le 10^9~

Ví dụ :

Input:

4 8
2 7 5 1

Output:

1 3 4

Một xâu gọi là xâu nhị phân nếu chỉ chứa hai ký tự "0" hoặc "1" Xâu v gọi là xâu con của w nếu xâu v có độ dài khác 0 và gồm các ký tự liên tiếp trong xâu w. Ví dụ: xâu "010" có các xâu con là "O", "1", "0", "01", ' "10", , "010".

Cho trước một giá trị k, hãy đếm xem có bao nhiêu xâu con chứa đúng k ký tự "1"

INPUT:

• Dòng 1 chứa một số nguyên k (1 ≤ k ≤ 10^6)

• Dòng 2 chứa một xâu nhị phân có độ dài ≤ 10^6

OUTPUT:

• Một số nguyên duy nhất là kết quả tìm được.

Ví dụ:

Input:

2
01010

Output:

4

Đội thi Robocon có N thanh thép rỗng với độ dài khác nhau. Thanh thứ i có độ dài L_i. Các em cần chọn ra đúng 3 thanh thép để hàn thành một khung hình tam giác sao cho chu vi của tam giác này là lớn nhất có thể. Biết điều kiện để 3 đoạn thẳng tạo thành tam giác là tổng độ dài 2 cạnh bất kỳ phải lớn hơn cạnh còn lại.

Dữ liệu vào:

Dòng 1: Số nguyên N (3 <= N <= 10^5).

Dòng 2: N số nguyên Li (1 <= Li <= 10^6).

Kết quả ra: Chu vi lớn nhất của tam giác tạo được. Nếu không thể tạo thành bất kỳ tam giác nào, in ra 0.

Ví dụ:

Input:

4
1 2 1 10

Output:

0

(Các thanh thép quá chênh lệch, không thể tạo tam giác).

Input:

5
3 6 2 3 4

Output:

13

(Chọn 3 thanh có độ dài 4, 3, 6).