Fişierul intrare/ieşire: | winetasting.in, winetasting.out | Sursă | IIOT 2021-22 Runda 3 |

Autor | Giorgio Audrito | Adăugată de | Stefan Dascalescu •stefdascalescu |

Timp execuţie pe test | 0.8 sec | Limită de memorie | 65536 kbytes |

Scorul tău | N/A | Dificultate | N/A |

Vezi solutiile trimise | Statistici

# Wine Tasting

There are `N` vineyards arranged in a row, numbered from `0` to `N-1`. Giorgio starts the tour from vineyard `L`, once the first tasting is over he will move on to the vineyard `L+1`, then to the vineyard `L+2` and so on until he reaches the vineyard `R`. Note that Giorgio can start and end his tour on the same vineyard.

To visit the vineyard `i` Giorgio has to pay `V[i]` euro. The cost of a tour is the cost of each vineyard visited.

There are a total of `N*(N+1)/2` different tours, Giorgio will choose one of the tours in the following way:

First, he sorts the tours in ascending order of cost, in case of a tie, the tours with the smallest starting vineyard come first. Then, he chose the `K`-th tour from this order.

Help Giorgio find the first and the last vineyards of the `K`-th tour!

## Date de intrare

The first line of the input file `winetasting.in` contains the integers `N` and `K`. The second line contains `N` integers `V[i]`.

## Date de ieşire

The output file `winetasting.out` contains a single line which has the integers `L` and `R`: the first and the last vineyards of Giorgio's tour.

## Restricţii

`1 ≤ N ≤ 2*10^5``1 ≤ K ≤ N*(N+1)/2``1 ≤ v[i] ≤ 10^9`- For tests worth
`50`points,`V[i]`=`1`for all values in the input. - For tests worth
`20`more points,`1 ≤ N ≤ 1000`.

## Exemplu

winetasting.in | winetasting.out |
---|---|

4 4 1 2 3 1 | 0 1 |

winetasting.in | winetasting.out |
---|---|

6 18 1 2 1 2 1 2 | 2 5 |

### Explicaţie

In the first sample case there are `10` possible tours, in order:

from `0` to `0`: the cost is `1`

from `3` to `3`: the cost is `1`

from `1` to `1`: the cost is `2`

from `0` to `1`: the cost is `1+2=3`

from `2` to `2`: the cost is `3`

from `2` to `3`: the cost is `3+1=4`

from `1` to `2`: the cost is `2+3=5`

from `0` to `2`: the cost is `1+2+3=6`

from `1` to `3`: the cost is `2+3+1=6`

from `0` to `3`: the cost is `1+2+3+1=7`

The fourth tour starts from vineyard `0` and end in vineyard `1`.