TopCoder

User's AC Ratio

64.7% (11/17)

Submission's AC Ratio

22.2% (34/153)

Description

「我與小明不相見已有二年餘了,我最不能忘記的是他的雙腿。(雖然他根本沒有)」

光陰荏苒,你如今是一位御用新聞記者,專門替國王烏龜的電視台採訪各式各樣的新聞。
還記得TIOJ 1623--國王烏龜的接駁車嗎?大意就是國王烏龜開放死老百姓烏龜們去覲見國王,
舉國上下無不歡聲雷動,一時之間各個直達皇宮接駁車的站牌前都排滿了烏龜,好不盛大!

你自然被派遣過去負責採訪這場盛宴。並且他們看在你的才能,決定要讓你Live連線報導,
你知道如果把這個難得的機會搞砸了你可能會變成小明第二。

因此,在開始報導之前你決定先去向前輩烏龜瞭解你的報導方式。

你待會要進行的報導方式呢,你看那邊有一條大排長龍的隊伍,共有n隻烏龜排成一列,
你需要選擇一個區間[A,B](包含A, B)進行採訪,採訪的方式是依序遞麥克風給這個區間每一隻烏龜,讓他們自由發言。
必須注意的是因為要弄得看起來很有公信力,你採訪的總人數不能小於L個人。

當然自由發言是有危險成份在的,有些反國王份子可能會講出危言聳聽的話,危害國王聲譽,
所以我們會依序把烏龜標號0或1,0表示危險份子、1則是很安全。

所以,我們希望你能讓這個區間內1佔的比例越大越好,如果有很多個一樣好的區間,
那就是總人數越少越好(但還是得>=L),如果還是有很多個,那就A越小越好。

你選好你要採訪的區間了嗎?告訴我吧。

Input Format

輸入第一行含一個正整數T,表示接下來有幾條隊伍要採訪(幾組詢問)
每組詢問第一行含兩個正整數n, L(L <= n),分別表示隊伍長度跟採訪總人數下限。
第二行會是一個長度為n的01序列,依序表現出每隻烏龜危不危險。

Output Format

對每組詢問輸出兩個正整數數字A和B,表示[A,B]是你的最佳選擇。
※這個序列編號由1開始,到n為止。

Sample Input

2
17 5
00101011011011010
20 4
11100111100111110000

Sample Output

7 11
6 9

Hints

對於第一組範例,[7,11]為11011,1的比例為80%,且他較[10,14]小。
對於第二組範例,[6,9]為1111,1的比例為100%,且他較[12,16]短。

對於100%測資,T <= 400; 1 <= L <= n。
對於10%測資,所有烏龜都不危險
對於30%測資,1 <= n <= 2,000
對於60%測資,1 <= n <= 5,000
對於80%測資,1 <= n <= 20,000
對於100%測資,1 <= n <= 100,000

Problem Source

原TIOJ1670 / 建國中學99年校內培訓contest #1 prob 5
problem setter:ATP
source:ACM-ICPC Regionals

Subtasks

For Testdata: 0 ~ 0, Score: 8
For Testdata: 1 ~ 1, Score: 8
For Testdata: 2 ~ 2, Score: 8
For Testdata: 3 ~ 3, Score: 8
For Testdata: 4 ~ 4, Score: 8
For Testdata: 5 ~ 5, Score: 8
For Testdata: 6 ~ 6, Score: 8
For Testdata: 7 ~ 7, Score: 8
For Testdata: 8 ~ 8, Score: 8
For Testdata: 9 ~ 9, Score: 8
For Testdata: 10 ~ 10, Score: 8
For Testdata: 11 ~ 11, Score: 12
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 3000 65536 262144
1 3000 65536 262144
2 3000 65536 262144
3 3000 65536 262144
4 3000 65536 262144
5 3000 65536 262144
6 3000 65536 262144
7 3000 65536 262144
8 3000 65536 262144
9 3000 65536 262144
10 3000 65536 262144
11 3000 65536 262144