Cho xâu ~S~ độ dài ~n~. Hãy tìm xâu con dài nhất của ~S~, sao cho mỗi ký tự tham gia vào xâu con không quá ~k~ lần (~1 ≤ n ≤ 100 000~, ~1 ≤ k ≤ n~).

Yêu cầu: Chỉ ra độ dài của xâu con tìm được và vị trí của ký tự đầu tiên thuộc xâu con trong xâu S ban đầu. Nếu có nhiều cách chọn xâu con – chỉ ra cách chọn xâu con với vị trí bắt đầu là nhỏ nhất.

Dữ liệu:

• Dòng đầu tiên chứa 2 số nguyên ~n~ và ~k~.

• Dòng thứ hai chứa xâu ~S~.

Kết quả:

• Một dòng chứa hai số nguyên: độ dài xâu con và vị trí ký tự đầu tiên của xâu con. Nếu có nhiều xâu con thì ghi vị trí của xâu con đầu tiên trong dãy.

Ví dụ:

Input

5 2
ababa

Output

4 1

Cho số nguyên dương k và một dãy gồm N số nguyên dương ~a_1, a_2, ..., a_N~. Hãy tìm số cặp số nguyên (~l~, ~r~) với ~1 ≤ l ≤ r ≤ N~ sao cho trong đoạn con từ ~a_l~ đến ~a_r~, có tối đa một số chia hết cho ~k~.

INPUT

• Dòng 1: ~N~, ~k~ (~1 ≤ N ≤ 3×10^5~, ~1 ≤ k ≤ 10^9~)
• Dòng 2: ~a_1, a_2, ... ,a_N~ (~1 ≤ a_i ≤ 10^9~)

OUTPUT

• Một số nguyên: số lượng cặp (~l~, ~r~) thỏa mãn điều kiện.

VÍ DỤ

Input:

5 2
1 2 3 4 5

Output:

11

Cho lần lượt 2 số nguyên dương n, k và mảng a có n phần tử, hãy tìm tổng lớn nhất trong các dãy con liên tiếp độ dài k trong mảng.

Input:

• Dòng 1. Ghi 2 số nguyên dương n,k.
• Dòng 2. Ghi n số nguyên

Output:

• In ra tổng lớn nhất của dãy số có độ dài k tìm được.

Example:

Input:

8 4
0 9 3 8 2 4 0 9

Output:

22

Constraints:

~1 \le k \le n \le 10^6, 0 \le |a_i| \le 10^9~

Sau khi thi giữa kì, vì đạt điểm số "cao", cụ thể là 5 6 7 8 nên Tèo được mẹ thưởng một chuyến đi du lịch ở "Dream Land".

Ở công viên giải trí "Dream Land", người ta có bán ~m~ vé khác nhau và mỗi loại vé được đánh số từ 1 tới ~m~. Các loại vé có giá tiền bằng nhau và chỉ còn bán với mỗi loại một lần sẽ có hiệu lực vĩnh viễn (sử dụng không giới hạn). Tèo được mẹ cho ~k~ ngày để giải trí tại đây, Tèo nghĩ rằng sẽ rất tệ nếu các ngày vui chơi bị gián đoạn nên Tèo mong muốn được vào khu vui chơi ~k~ ngày liên tiếp. Tèo được cung cấp một dãy ~n~ số nguyên ~a₁, a₂, ..., aₙ~ ~(1 ≤ aᵢ ≤ ~m) cho biết loại vé cần thiết vào ngày thứ ~i~.

Yêu cầu: Hãy giúp Tèo tìm số lượng vé ít nhất phải mua để có thể vào "Dream Land" vui chơi ~k~ ngày liên tiếp.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~t~ (~1 ≤ t ≤ 100~) là số bộ test, trong mỗi bộ test:

• Dòng đầu tiên chứa ba số nguyên dương ~n~, ~m~, ~k~ (~1 ≤ n, m, k ≤ 10^5~, ~k ≤ n~).

• Dòng thứ hai chứa n số nguyên ~a₁, a₂, ..., aₙ~ ~(1 ≤ aᵢ ≤ m~).

• Tổng ~n~ trong tất cả các test không quá ~10^5~.

Kết quả ra

• Một dòng duy nhất chứa số lượng vé ít nhất phải mua thỏa yêu cầu đề bài.

Ví dụ:

Input

3
10 6 6
6 1 6 4 4 6 5 3 4 4
8 2 4
2 1 2 1 2 1 2 1
1 4 1
3

Output

3
2
1

Giải thích

• Ở test đầu tiên, Tèo chọn đi chơi từ ngày 1 đến ngày 6 và cần 3 loại vé là 1, 6, 4.

• Ở test thứ hai, Tèo có thể chọn 4 ngày liên tiếp bất kỳ và cần 2 loại vé là 1, 2.

• Ở test cuối, Tèo chỉ có một lựa chọn duy nhất là mua 1 loại vé số 3.

Mật khẩu là một xâu ký tự. Một mật khẩu được gọi là an toàn nếu thoả mãn các điều kiện sau:

• Có độ dài ít nhất bằng 8
• Chứa ít nhất một chữ cái in hoa ['A'..'Z']
• Chứa ít nhất một chữ cái in thường ['a'..'z']
• Chứa ít nhất một chữ số ['0'..'9']

Cho một xâu ký tự có độ dài không quá 1000 ký tự.

Yêu cầu: Hãy xác định có bao nhiêu đoạn con gồm các ký tự liên tiếp nhau trong xâu S có thể chọn làm mật khẩu an toàn.

Input:

Được cho bởi tệp MATKHAU.INP có cấu trúc như sau:

• Dòng 1: Ghi xâu ký tự S

Output

Ghi ra tệp MATKHAU.OUT theo cấu trúc:

• Dòng 1. Ghi số nguyên dương t là kết quả tìm được theo yêu cầu.

Example

Input

ABC123abc

Output

3

Input

ABC123

Output

0

Constrains:

• Có 50% số test ứng với độ dài xâu ~S \le 50~
• Có 30% số test ứng với độ dài xâu ~50 \le S \le 300~
• Có 20% số test ứng với độ dài xâu ~300 \le S \le 1000~

Nhân dịp kỉ niệm 1 năm thành lập, Câu lạc bộ tin học qboj tổ chức trò chơi "Dãy con kì diệu" dành cho các thành viên.

Trò chơi được tổ chức như sau:

Cho trước dãy số ~A~ gồm có ~𝑛~ phần tử là số nguyên dương có giá trị không vượt quá ~10^9~ và số ~𝑡~. Một dãy con ~𝑎_ℎ,𝑎_{ℎ+1},…,𝑎_{𝑟-1},𝑎_𝑟~ của dãy số ~A~ được xem là dãy con kì diệu nếu với mỗi cặp (~𝑖,𝑗~) thỏa mãn ~ℎ < 𝑖 < 𝑗 < 𝑟~ và ~|𝑎_𝑖-𝑎_𝑗|≤𝑡~. Hãy tìm dãy con kì diệu dài nhất của dãy số ~A~, độ dài dãy con đó chính là giá trị món quà mà người thắng cuộc (tức là người tìm đúng và nhanh nhất) sẽ nhận được.

Hãy giúp ban tổ chức trong việc chuẩn bị quà một cách nhanh nhất.

Dữ liệu vào:

• Dòng đầu tiên ghi 2 số ~𝑛~ và ~𝑡~ (~1 ≤ 𝑛 ≤ 10^6,0 ≤ t ≤ 10^7~);

• Dòng thứ hai ghi ~𝑛~ số nguyên dương là giá trị ~𝑛~ phần tử của dãy số ~𝑎~;

• Các số trên mỗi dòng được ghi cách nhau ít nhất một ký tự trống.

Kết quả:

• Một số duy nhất là độ dài của dãy con kì diệu dài nhất tìm được của dãy số ~A~. Nếu không tìm được dãy thoả mãn thì in ra số 0.

Ví dụ

Input

9  3
15  1  3  5  8  6  7  9  10

Output

4

Cho dãy số ~a_1,a_2,…,a_n~. Đếm số đoạn con liên tiếp có tổng không lớn hơn ~k~.

Lưu ý: 1 phần tử cũng được tính 1 đoạn con.

Dữ liệu vào:

• Dòng đầu tiên gồm 2 số nguyên dương ~n~ và ~k~. (~n≤10^6,1≤k≤10^9~)
• Dòng tiếp theo ghi ~n~ số lần lượt là ~a_1,a_2,…,a_n~. (~1 ≤ a_i≤10^9~)

Dữ liệu ra:

• Ghi số nguyên dương ~x~ duy nhất là số đoạn con có tổng không lớn hơn ~k~.

Ví dụ

Input:

5 100 
124 1 94 15 20

Output:

6