C. Sales
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

For a company to know if it is doing well or poorly in sales, it is important to analyze the average sales over a period of time.

As a sales analyst, you observe $$$K$$$ consecutive months intervals and find the average. You are interested in the first interval with the lowest average and the first with the highest average.

Formally, we can represent sales as a list $$$v_1,v_2...v_n$$$, where $$$v_i$$$ means how many items were sold in month $$$i$$$. An interval that starts in month $$$i$$$ and has size $$$K$$$ encompasses the elements $$$v_i,v_{i+1}...v_{i+K-1}$$$ and has average $$$\frac{(v_i + v_{i+1}...+v_{i+K-1})}{K}$$$.

For example, if $$$v = \{ 1,\ 1, \ 1,\ 2, \ 3 \}$$$ and $$$K=2$$$, the first interval with the lowest average starts at $$$i=1$$$, $$$\frac{(v_1 + v_2)}{2} = \frac{(1+1)}{2} = 1$$$, and the one with the highest average starts at $$$i=4$$$, $$$\frac{(v_4+v_5)}{2} = \frac{(2+3)}{2} = 2.5$$$. Note that the interval starting at $$$i=2$$$ also has an average of 1, but it is not the first interval with the lowest average. Also note that $$$i=5$$$ does not delimit a valid interval, as we do not yet know the number of sales in month 6.

Input

The first line contains two integers $$$N, K$$$, the number of elements in the sales list and the interval size. It is guaranteed that $$$1 \leq K \leq N \leq 10^5$$$.

The next line contains $$$N$$$ integers $$$v_1, v_2 ... v_N$$$, representing the sales list. It is guaranteed that $$$1 \leq v_i \leq 10^4$$$.

Output

Print a line with two integers: the index of the start of the first interval with the lowest and the highest average.

Due to large constraints, if you are receiving Time Limit Exceeding it may be useful to try another approach.

Examples
Input
5 2
1 1 1 2 3
Output
1 4
Input
6 4
1000 1 2 3 4 100
Output
2 1