Với dãy số nguyên dương \(A = (a_1, a_2, \dots, a_n)\) và số nguyên dương \(k\), tạo dãy \(A^k\) gồm \(m = n \times k\) phần tử bằng cách ghép liên tiếp \(k\) lần dãy \(A\), cụ thể \(A^k = (a_1, a_2, \dots, a_n, \dots, a_1, a_2, \dots, a_n)\). Một đoạn \(d\) phần tử liên tiếp trên dãy \(A^k\) bắt đầu từ phần tử thứ \(i\) (\(1 \le i \le m-d+1\)) gồm các phần tử \(i, i+1, \dots, (i+d-1)\) được gọi là đoạn đẹp nếu điều kiện sau thỏa mãn:

Yêu cầu: Cho \(A = (a_1, a_2, \dots, a_n)\) và hai số nguyên dương \(k, d\), hãy đếm chỉ số \(i\) (\(1 \le i \le m-d+1\)) mà đoạn gồm \(d\) phần tử liên tiếp bắt đầu từ phần tử \(i\) là đoạn đẹp trên dãy \(A^k\).

Input

• Dòng đầu chứa ba số nguyên dương \(n, k, d\) (\(n, k \le 10^5; d \le n \times k\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^6\)).

Output

• Một dòng chứa một số nguyên là số chỉ số \(i\) cần đếm.

Example

2 3 3
1 3

2

3 10 3
1 5 10

0

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \times k \le 3 \times 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \times k \le 4 \times 10^5\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \times k \le 5 \times 10^7\).
• Subtask \(4\) (\(10\%\) số điểm): không có ràng buộc gì thêm.