GC-Ratio

A DNA sequence is made up of the letters A, C, G, and T. The GC-ratio of a DNA sequence is the number of C and G divided by the length of the sequence. Regions with a high GC-ratio are more likely to be the start of a gene, so the GC-ratio is an important measure.

Research often looks for the substring (a contiguous segment) with the largest GC-ratio inside a very long DNA sequence. Because short substrings with a high GC-ratio are usually meaningless, a lower bound $L$ on the length is fixed, and only substrings of length at least $L$ are considered.

If every A and T is replaced by $0$ and every C and G by $1$, the DNA sequence becomes a binary sequence of the same length. The average value of this binary sequence equals the GC-ratio of the original DNA sequence.

For the binary sequence above, if the lower bound is $7$, the substring with the maximum average is $[7, 14]$ with average $6/8$. If the lower bound is $5$, the substring with the maximum average is $[7, 11]$ with average $4/5$.

Given a binary sequence and a length lower bound $L$, write a program that finds the substring with the maximum average among all substrings of length at least $L$. If several substrings share the maximum average, choose the one with the shortest length; if several of those exist, choose the one with the earliest starting position.

The first line contains the number of test cases $T$. Each test case consists of two lines. The first line contains the length of the binary sequence $n$ and the length lower bound $L$ ($1 \le n \le 100{,}000$, $1 \le L \le 1{,}000$). The second line contains the binary sequence of length $n$.

For each test case, print the starting position and the ending position of the chosen substring on one line, separated by a space. Positions are counted from $1$.