Bạn được nhận một xâu ~A~ gồm ~n~ kí tự Latin in thường và một số nguyên dương ~k~. Ta xây dựng xâu ~S = A \times k~, tức là xâu ~S~ được xây dựng bằng cách viết ra ~k~ lần xâu ~A~.

Để tăng độ yêu trường cho học sinh, ~mrtee~ quyết định giao cho các học sinh công việc đếm các xâu kí tự có dạng ams xuất hiện trong ~S~ dưới dạng một xâu con liên tiếp.

Ví dụ: ~A = amser~, ~k = 2~ ~\Rightarrow S = amseramser~. Có ~2~ xâu con liên tiếp của ~S~ bằng ams.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,k~ ~(1 \le n \le 2 \times 10^5)~
• Dòng thứ ~2~ là xâu ~A~ gồm ~n~ phần tử.

Output:

• In ra số lượng xâu con liên tiếp bằng ams xuất hiện trong ~S~.

Subtask:

• Subtask ~1~ (~50\%~ số điểm): ~k = 1~.
• Subtask ~2~ (~50\%~ số điểm): Không có giới hạn gì thêm.

Sample Input 1

5 2
amser

Sample Output 1

2

Sample Input 2

3 2
msa

Sample Output 2

1

Trong một cơ quan, có ~𝑁~ yêu cầu sử dụng phòng họp trực tuyến. Cơ quan đã đăng kí với cấp trên đường truyền ưu tiên theo ~𝑀~ mốc thời gian được đánh số từ ~1~ đến ~M~. Mỗi yêu cầu đăng kí sử dụng phòng họp trong các mốc thời gian liên tiếp từ ~𝐿~ đến ~𝑅~ ~(1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑀)~. Để tiện cho việc sắp xếp và phục vụ các phòng họp, cần biết mỗi yêu cầu xung đột với bao nhiêu yêu cầu khác (hai yêu cầu gọi là xung đột với nhau nếu có chung ít nhất một mốc thời gian).

Yêu cầu: Cho biết ~𝑁~ yêu cầu sử dụng phòng họp. Với mỗi yêu cầu, hãy tính số lượng yêu cầu xung đột với nó.

Dữ liệu nhập vào từ file văn bản XPH.INP:

• Dòng đầu chứa số hai nguyên ~𝑁,𝑀~ ~(1 ≤ 𝑁 ≤ 2 \times 10^5; \ 1 ≤ 𝑀 ≤ 10^9)~ là số lượng yêu cầu và số lượng mốc thời gian~;~
• ~N~ dòng tiếp theo, dòng thứ ~𝑖~ chứa hai số nguyên ~𝐿_i,𝑅_i \ (1 ≤ 𝐿_i ≤ 𝑅_i ≤ 𝑀; \ 1 ≤ 𝑖 ≤ 𝑁)~ là mốc thời gian bắt đầu và kết thúc của yêu cầu thứ ~𝑖~.

Kết quả ghi ra file văn bản XPH.OUT:

Gồm ~𝑁~ dòng, dòng thứ ~𝑖~ mô tả số lượng yêu cầu xung đột với yêu cầu thứ ~𝑖~ ~(1 ≤ 𝑖 ≤ 𝑁)~.

Ràng buộc

• Có ~25\%~ số test ứng với ~25\%~ số điểm của bài thoả mãn: ~𝑁, 𝑀 ≤ 400;~
• ~25\%~ số test khác ứng với ~25\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 2000;~
• ~25\%~ số test khác ứng với ~25\%~ số điểm của bài thoả mãn: ~𝑀 ≤ 4 \times 10^5;~
• ~25\%~ số test còn lại ứng với ~25\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5 7
1 2
2 5
3 5
7 7
4 6

Output

1
3
2
0
2

Một xâu ~S~ được gọi là xâu đối xứng nếu ~S = S'~ với ~S'~ là xâu nhận được từ xâu ~S~ khi đọc từ phải qua trái. Ví dụ: Xâu ~'aba'~ là xâu đối xứng, còn xâu ~'abc'~ là xâu không đối xứng.

Cho một xâu ~S~ gồm ~1 \le n \le 1000~ kí tự.

Yêu cầu: Hãy tìm cách chia xâu ~S~ thành ít nhất các đoạn mà mỗi đoạn đều là các xâu đối xứng.

Input

• Dòng đầu gồm một số nguyên ~n~ là độ dài của xâu ~S~.
• Dòng thứ hai là nội dung xâu ~S~.

Output

• Dòng đầu ghi một số nguyên ~k~ (số đoạn ít nhất tìm được).
• ~K~ dòng sau, mỗi dòng ghi một số nguyên ~t_i~, với ~t_i~ là vị trí kết thúc của đoạn thứ ~i~.

Sample Input 1

 8
 abbacdcb

Sample Output 1

3
4
7
8

Khôi có một dãy ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Một dãy con ~a_l, a_{l + 1}, \dots, a_{r}~ được gọi là pro nếu

• ~a_i + 1 = a_{i + 1},\ \forall l \le i \lt r~.

Ví dụ ~a = [1, 3, 4, 5, 2]~, thì dãy con ~[3, 4, 5]~ là dãy pro, dãy con ~[3]~ là dãy pro, nhưng dãy ~[3, 4, 5, 2]~ thì không. Chú ý dãy con có một phần tử cũng được gọi là pro.

Khôi định nghĩa độ pro của dãy ~a~ là dãy con dài nhất của ~a~ mà là dãy pro. Trong ví dụ trên, độ pro của dãy ~a = [1, 3, 4, 5, 2]~ là ~3~.

Để làm cho dãy số của mình trở nên pro nhất có thể, Khôi sẽ thực hiện tối đa ~k~ lần chỉnh sửa, mỗi lần chọn một vị trí ~i~, và tăng hoặc giảm ~a_i~ đi ~1~ đơn vị. Trong tất cả các cách chỉnh sửa có thể, Khôi muốn chọn ra cách có độ pro lớn nhất. Vì Khôi khá ga` nên hãy giúp Khôi tìm ra độ pro có thể này nhé!

Input (vào từ file văn bản proseq.inp)

• Dòng đầu chứa hai số nguyên ~n, k~ ~(1 \le n \le 5 \times 10^5,\ 0 \le k \le 10^{15})~.
• Dòng sau chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(|a_i| \le 10^9)~.

Output (ghi ra file văn bản proseq.out)

• In ra một sô nguyên duy nhất là độ pro lớn nhất có thể sau khi thực hiện tối đa ~k~ lần chỉnh sửa.

Subtasks

• Subtask 1 (~20\%~ số điểm): ~k = 0~.
• Subtask 2 (~20\%~ số điểm): ~n \le 500~.
• Subtask 3 (~30\%~ số điểm): ~n \le 5000~
• Subtask 4 (~30\%~ số điểm): Không có điều kiện gì thêm.

Sample Input 1

5 0
1 3 4 2 5

Sample Output 1

2

Notes: Ta không thể thực hiện bước chỉnh sửa nào, nên dãy ~a~ giữ nguyên và có độ pro là ~2~.

Sample Input 2

6 5
2 0 3 3 6 8

Sample Output 2

5

Notes: Ta có thể biến dãy ~a~ về ~[1, 2, 3, 4, 5, 8]~ và có độ pro là ~5~.