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.4 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

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.

Cum se trimit solutii?