Cho một xâu ~S~ gồm các kí tự số. Hãy đếm xem có bao nhiêu xâu con chia hết cho ~4~ (xâu con có thể bắt đầu bằng ~0~).

Input:

Xâu ~S~ có độ dài không quá ~10^6~.

Output:

In ra kết quả của bài toán.

Scoring

• Subtask 1 [60%]: Xâu ~S~ có độ dài không quá ~100~.
• Subtask 2 [40%]: Không có ràng buộc gì thêm.

Examples

Input1

08

Output1

3

Giải thích

~0, 8, 08~

Input2

13085

Output2

5

Cho dãy số ~A~ gồm ~N~ phần tử nguyên dương và một số nguyên dương ~K~. Tìm hai dãy con liên tiếp của dãy ~A~, mỗi dãy gồm đúng ~K~ phần tử (hai dãy không giao nhau), sao cho chênh lệch tổng các phần tử của hai dãy là lớn nhất.

Input:

• Dòng đầu tiên gồm hai số nguyên dương ~N, K~ ~(2 \le N \le 10^6, 1 \le K \le N / 2)~;
• Dòng thứ hai gồm ~N~ số nguyên dương có giá trị không quá ~10^9~ mô tả dãy số ~A~.

Output:

• In ra một số nguyên dương là giá trị chênh lệch lớn nhất tìm được.

Scoring:

• Subtask ~1~ ~(60\%)~: ~ N \le 100~;
• Subtask ~2~ ~(20\%)~: ~ N \le 10^3 ~;
• Subtask ~3~ ~(20\%)~: Không có giới hạn gì thêm.

Sample Input 1

5 2
1 3 2 1 8

Sample Output 1

5

Tewi đã ốm liệt giường nên Yagokoro Eirin phải chữa bệnh cho cô. Đoạn ADN của Tewi có độ dài ~n~ gồm cách kí tự ~a, b, c~ (vì sao thì chưa rõ). Eirin có thể sửa đổi một vị trí bất kì trên ADN với chi phí là 1.

Cô đang nghi ngờ ~q~ đoạn con ~[l_i, r_i]~ có thể là nguyên nhân gây bệnh. Với mỗi đoạn ADN con này, Eirin muốn sửa lại đoạn này sao cho không tồn tại đoạn con nào có độ dài lớn hơn 1 là xâu đối xứng. Ví dụ ~aab~ là không thỏa mãn vì có ~aa~ là xâu đối xứng. Hãy giúp cô tính trước chi phí để chữa bệnh nhé!

Input:

• Dòng đầu tiên gồm 2 số ~n, q~.
• Dòng tiếp theo là một xâu gồm ~n~ kí tự chỉ gồm ~a, b, c~.
• ~q~ dòng tiếp theo mỗi dòng gồm 2 số ~l_i, r_i~.

Output:

• ~q~ dòng là chi phí chữa bệnh.

Sample Test

Input:

5 4
baacb
1 3
1 5
4 5
2 3

Output:

1
2
0
1

Giới hạn:

• Trong mọi test ~n, q \le 10^5~
• 10% số điểm: ~n, q \le 5~.
• 30% số điểm: ~n, q \le 2000~.
• 30% số điểm: ADN chỉ gồm 2 kí tự ~a, b~.
• 30% số điểm: Không có giới hạn gì thêm.

Cho một xâu ~s~ có độ dài ~n~ chỉ bao gồm các kí tự ~a,b,c~. Một đoạn ~[l,r]~ được gọi là tốt khi và chỉ khi có một kí tự trong đoạn có số lần xuất hiện lớn hơn một nửa độ dài đoạn. Nói cách khác, gọi ~cnt(d,l,r)~ là số lần xuất hiện của kí tự ~d~ trong đoạn ~[l,r]~, ta cần tồn tại một kí tự ~d~ trong đoạn ~[l,r]~ sao cho ~cnt(d,l,r) > (r-l+1)/2~. (Với ~d~ thuộc ~[a,b,c]~)

Hãy in ra độ dài đoạn tốt lớn nhất.

Input

• Dòng đầu gồm số nguyên dương ~n~ miêu tả độ dài xâu. ~(1 \le n \le 10^5)~
• Dòng thứ hai miêu tả xâu ~s~. Xâu ~s~ chỉ bao gồm các kí tự ~a,b,c~ và có độ dài ~n~.

• Ouput

• In ra độ dài đoạn tốt lớn nhất.

Sample Test

Input

7
aabbbcc

Output

5

Giải thích: Chọn đoạn ~[1,5]~.

Alice vừa mới lạc vào một vùng đất rất kì lạ tên là "Bruhderland". Đây là một vùng đất lai giữa "Wonderland" và "Borderland", nơi có phép màu và cả những trò chơi sinh tử.

Bruhderland được biểu diễn bằng một ma trận ~n \times m~, với ô ~(i,j)~ là một trong các kí tự sau:

• .: có nghĩa là ô đất trống, có thể đi vào.
• *: có nghĩa là ô có một tảng đá, không thể đi vào.
• A: có nghĩa là có một trò chơi với độ khó ~A~ ở ô này, Alice rất giỏi nên sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~1~ sức lực.
• B: có nghĩa là có một trò chơi với độ khó ~B~ ở ô này, Alice vẫn sẽ có thể vượt qua trò chơi, nhưng sẽ mất ~2~ sức lực.

Giả sử, Alice đang ở ô ~(i,j)~, cô có thể đi sang ~4~ ô kề cạnh nếu như ô đó không vượt qua ngoài bảng và không chứa tảng đá nào. Như đã nói, Bruhderland có cả yếu tố phép màu, vậy nên khi vào đây, cô đã học được cách đọc thần chú để phá hủy một tảng đá bất kì mà không mất sức lực nào (nghĩa là có thể đi vào ô chứa tảng đá vừa bị phá hủy), tuy nhiên do năng lực giới hạn, Alice chỉ có thể đọc thần chú ~k~ lần mà thôi.

Alice đang ở ô ~(1,1)~, để thoát ra khỏi Bruhderland, cô sẽ cần đến ô ~(n,m)~. Tuy nhiên, do khá lười tham gia vào các trò chơi, Alice muốn thoát ra khỏi Bruhderland sao cho tốn ít sức lực nhất.

Quan trọng: Dữ liệu đảm bảo kết quả không quá ~2500~.

Input: BRUHDERLAND.INP

• Dòng đầu tiên ghi ~3~ số nguyên dương ~n,m,k~ ~(1 \le n,m \le 1000, 0 \le k \le 5)~.
• ~n~ dòng sau, dòng thứ ~i~ gồm một xâu kí tự độ dài ~m~ miêu tả hàng thứ ~i~ của ma trận.
• Dữ liệu đảm bảo ô ~(1,1)~ là kí tự . và luôn tồn tại cách đi từ ~(1,1)~ tới ~(n,m)~ nếu sử dụng thần chú một cách hợp lý.

Output: BRUHDERLAND.OUT

• In ra một số nguyên dương là số sức lực ít nhất cần tiêu tốn để đến được ô ~(n,m)~.

Scoring:

• Subtask ~1~ ~(10\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ chỉ gồm kí tự A
• Subtask ~2~ ~(15\%)~: ~ n\times m \le 10^5~, ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B và ..
• Subtask ~3~ ~(10\%)~: ~k = 0~ và các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~4~ ~(10\%)~: Các ô khác ô ~(1,1)~ không có kí tự B.
• Subtask ~5~ ~(15\%)~: ~n \times m \le 10^5~ và ~k = 0~.
• Subtask ~6~ ~(20\%)~: ~n \times m \le 10^5~.
• Subtask ~7~ ~(20\%)~: Không có giới hạn gì thêm.

Sample Input 1

4 4 0
.AAA
AAAA
AAAA
AAAA

Sample Output 1

6

Sample Input 2

5 4 0
.AAA
***A
AAAA
A***
AAAA

Sample Output 2

13

Sample Input 3

5 4 0
.AAA
***B
AAAA
A**B
BAAA

Sample Output 3

9

Sample Input 4

5 4 2
.BAA
****
AABA
A***
BABA

Sample Output 4

6

Chim là loài động vật đại diện cho sự tự do. Châu có nuôi 1 con chim tên là Ển, hiện đang sống tại tọa độ ~(0, 0)~ trên mặt phẳng Descartes và hướng về phía dương của trục ~Ox~. Châu đang có một chuỗi thao tác gồm một số thao tác xác định và chưa xác định:

• ~F~ là 1 thao tác cố định yêu cầu chim đi chuyển 1 đơn vị về hướng hiện tại.
• ~T~ là 1 thao tác chưa xác định. Bạn có thể chọn T là cho chim quay theo chiều kim đồng hồ 90 độ hoặc cho chim quay theo ngược chiều kim đồng hộ 90 độ.

Có ~Q~ truy vấn tương ứng là ~Q~ tọa độ ~(x,y)~. Châu muốn biết xem có thể chọn các thao tác ~T~ tương ứng để chim đến được tọa độ ~(x,y)~ không.

Input:

• Dòng đầu tiên là ~Q~ – số lượng truy vấn.
• Dòng thứ hai là xâu biểu diện các thao tác.
• ~Q~ dòng tiếp theo mỗi dòng chứa tọa độ ~(x,y)~.

Output:

• Dòng thứ ~i~ trả về YES nếu chim có thể đến được ~(x,y)~ ở truy vấn thứ ~i~, ngược lại NO.

Sample Test

Input:

2
FTFFTFF
3 2
0 1

Output:

Yes
No

Giới hạn:

• Subtask 1 (20% số điểm): Độ dài các xâu không vượt quá ~20~ kí tự, ~Q \le 20~.
• Subtask 2 (40% số điểm): Độ dài các xâu không vượt quá ~100~ kí tự, ~Q \le 100~.
• Subtask 3 (40% số điểm): Độ dài các xâu không vượt quá ~4000~ kí tự, ~Q \le 10^5~.