GC-비율

DNA 수열은 문자 A, C, G, T로 이루어진다. DNA 수열의 GC-비율은 (C와 G의 개수)를 (수열의 길이)로 나눈 값이다. GC-비율이 높은 구간은 유전자의 시작 구간일 확률이 높으므로, GC-비율은 중요한 지표이다.

매우 긴 DNA 수열에서 GC-비율이 가장 큰 부분 수열(연속한 구간)을 찾는 연구가 활발하다. 다만 GC-비율이 높은 짧은 부분 수열은 의미가 없는 경우가 많으므로, 길이의 하한 $L$을 정해 두고 길이가 $L$ 이상인 부분 수열만 대상으로 한다.

DNA 수열에서 A와 T를 모두 $0$으로, C와 G를 모두 $1$로 바꾸면 같은 길이의 이진수열을 얻는다. 이렇게 만든 이진수열의 평균값은 원래 DNA 수열의 GC-비율과 같다.

위와 같은 이진수열에서 길이의 하한이 $7$이면 평균이 최대인 부분 수열은 $[7, 14]$이고 평균은 $6/8$이다. 하한이 $5$이면 평균이 최대인 부분 수열은 $[7, 11]$이고 평균은 $4/5$이다.

이진수열과 길이의 하한 $L$이 주어질 때, 길이가 $L$ 이상인 모든 부분 수열 중에서 평균이 최대인 부분 수열을 찾는 프로그램을 작성하시오. 평균이 최대인 부분 수열이 여러 개이면 그중 길이가 가장 짧은 것을, 길이가 가장 짧은 것이 여러 개이면 시작 위치가 가장 앞선 것을 답으로 한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 이진수열의 길이 $n$과 길이의 하한 $L$이 주어지고 ($1 \le n \le 100{,}000$, $1 \le L \le 1{,}000$), 둘째 줄에는 길이가 $n$인 이진수열이 주어진다.

각 테스트 케이스마다 선택한 부분 수열의 시작 위치와 끝 위치를 공백으로 구분하여 한 줄에 출력한다. 위치는 $1$부터 센다.