Thuật toán nén dữ liệu tạo ra một số nguyên khổng lồ có N chữ số. Để số này có thể lưu trữ hợp lệ trong hệ thống mới, nó bắt buộc phải chia hết cho 3. Bạn được phép xóa đi một số ít nhất các chữ số (có thể không xóa chữ số nào) để số còn lại thỏa mãn điều kiện chia hết cho 3. Hãy in ra số lượng chữ số ít nhất cần phải xóa. Dữ liệu đảm bảo luôn có cách xóa để số còn lại khác rỗng.

Input:

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

Dòng 2: Một chuỗi N chữ số (không bắt đầu bằng chữ số 0).

Output: Số lượng chữ số cần xóa ít nhất.

Ví dụ:

Input:

4
1234

Output:

1

(Giải thích: Xóa chữ số 1 thành 234, hoặc xóa 4 thành 123).

Một xâu ký tự S được gửi qua mạng thường bị chèn các mã rác. Mã rác được định nghĩa là các chuỗi con "AB" hoặc "CD". Hệ thống tường lửa sẽ tự động quét và xóa các chuỗi con "AB" và "CD" khỏi S. Quá trình này diễn ra lặp đi lặp lại cho đến khi trong S không còn bất kỳ chuỗi "AB" hay "CD" nào nữa. Hãy tính độ dài của xâu S sau khi đã được tường lửa dọn dẹp sạch sẽ.

Input: Một dòng chứa xâu S chỉ gồm các ký tự in hoa (Độ dài <= 2*10^5).

Output: Độ dài xâu S còn lại.

Ví dụ:

Input:

CABABD

Output:

0

(Giải thích: Xóa "AB" ở giữa -> CABD. Xóa tiếp "AB" -> CD. Xóa tiếp "CD" -> rỗng).

Bản đồ quy hoạch thành phố là một lưới kích thước N dòng, M cột. Mỗi ô mang một giá trị lợi nhuận (có thể âm, thể hiện việc thua lỗ nếu xây dựng trên đó). Một tập đoàn bất động sản muốn mua một khu đất hình chữ nhật trên lưới này sao cho tổng lợi nhuận của các ô trong khu đất đó là lớn nhất có thể. Hãy tính mức lợi nhuận cực đại đó.

Input:

Dòng 1: N, M (1 <= N, M <= 100).

N dòng tiếp theo: Mỗi dòng M số nguyên Aij (|Aij| <= 10^4).

Output: Lợi nhuận lớn nhất của một hình chữ nhật con.

Ví dụ:

Input:

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

Output:

11

Cho hai đoạn thẳng AB và CD trên mặt phẳng. Hãy kiểm tra xem hai đoạn thẳng này có cắt nhau (có điểm chung) hay không. Lưu ý trường hợp hai đoạn thẳng trùng nhau một phần hoặc nối tiếp nhau vẫn tính là cắt nhau.

Đầu vào: 8 số nguyên xA, yA, xB, yB, xC, yC, xD, yD (-10^6 <= x, y <= 10^6).

Đầu ra: In ra YES nếu hai đoạn thẳng có điểm chung, ngược lại in ra NO.

Input:

0 0 4 4 0 4 4 0

Output:

YES