원형 마을의 도둑

N개의 집이 순서대로 이웃해 늘어선 마을이 있다. 첫 번째 집과 마지막 집도 서로 이웃하므로, 집은 하나의 원을 이룬다.

위 그림은 N = 8인 마을이다. 3이 적힌 집은 9가 적힌 집, 4가 적힌 집과 이웃하고, 5가 적힌 집은 6이 적힌 집, 7이 적힌 집과 이웃한다. 마을 사람은 각자 자기 집에 돈을 보관하며, 집에 적힌 숫자가 그 집이 보관 중인 돈의 액수다.

어느 날 이 마을에 도둑이 들었다. 도둑은 빠르게 훔치고 달아나려고 이웃한 M개의 집을 골라 그 집이 보관 중인 돈을 전부 훔치기로 했다. M = 3이면 3, 4, 7을 보관한 집에서 14를 훔친 뒤 달아나거나, 5, 6, 4를 보관한 집에서 15를 훔친 뒤 달아난다.

그런데 훔친 돈의 합이 K원 이상이 되면 자동 방범장치가 작동해 도둑은 그 자리에서 붙잡힌다. M = 3, K = 15인 경우 3, 4, 7을 보관한 집을 고르면 훔친 돈이 14라서 무사히 달아나지만, 5, 6, 4를 보관한 집을 고르면 훔친 돈이 15가 되어 붙잡힌다.

집의 개수 N, 도둑이 돈을 훔칠 연속된 집의 개수 M, 방범장치가 작동하는 최소 금액 K, 각 집이 보관 중인 돈이 주어질 때, 도둑이 붙잡히지 않고 달아나는 선택이 몇 가지인지 구하는 프로그램을 작성하시오. 선택은 도둑질을 시작하는 집으로 구분한다. 시작하는 집이 N가지이므로 후보도 N가지이고, M = N이어도 시작하는 집이 다르면 서로 다른 선택으로 센다.

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스의 첫째 줄에는 마을에 있는 집의 개수 N($1 \le N \le 100{,}000$), 도둑이 돈을 훔칠 연속된 집의 개수 M($1 \le M \le N$), 자동 방범장치가 작동하는 최소 금액 K($1 \le K \le 1{,}000{,}000{,}000$, K는 정수)가 공백으로 구분되어 주어진다.

둘째 줄에는 N개의 집이 보관 중인 돈이 시계 방향 순서대로 공백으로 구분되어 주어진다. 입력의 첫 번째 값과 마지막 값에 해당하는 두 집도 서로 이웃한다. 각 집이 보관 중인 돈은 1 이상 10,000 이하의 정수다.

출력은 표준 출력을 사용한다. 각 테스트 케이스마다 도둑이 자동 방범장치에 붙잡히지 않고 연속된 M개의 집에서 돈을 훔치는 선택의 수를 한 줄에 하나씩 출력한다.