galeti

Avem n găleți, numerotate de la stânga la dreapta cu numere de la 1 la n. Fiecare găleată conține inițial 1 litru de apă. Capacitatea fiecărei găleți este nelimitată. Vărsăm gălețile una în alta, respectând o anumită regulă, până când toată apa ajunge în prima găleată din stânga. Vărsarea unei găleți presupune un anumit efort.

Regula după care se răstoarnă gălețile este următoarea: se aleg două găleți astfel încât orice găleată situată între ele să fie goală. Se varsă apa din găleata din dreapta în găleata din stânga. Efortul depus este egal cu volumul de apă din găleata din dreapta ( cea care se varsă).

Formal, dacă notăm $a_i$ volumul de apă conținut în găleata cu numărul i, regula de vărsare a acestei găleți în găleata cu numărul j poate fi descrisă astfel:

1. j<i
2. $a_k=0$ pentru orice k astfel încât j<k<i
3. efortul depus este $a_i$
4. după vărsare $a_j=a_j+a_i$ și $a_i=0$

Cerinţe

Cunoscând numărul de găleți n și un număr natural e, să se determine o succesiune de vărsări în urma căreia toată apa ajunge în găleata cea mai din stânga și efortul total depus este exact e.

Date de intrare

Fișierul de intrare galeti.in conține pe prima linie două numere naturale, n și e, în această ordine, separate prin spațiu. Primul număr n reprezintă numărul de găleți. Al doilea număr e reprezintă efortul care trebuie depus pentru a vărsa toată apa în găleata din stânga.

Date de ieşire

Fișierul de ieșire galeti.out trebuie să conțină n-1 linii care descriu vărsările, în ordinea în care acestea se efectuează, pentru a vărsa toată apa în găleata din stânga cu efortul total e. Fiecare dintre aceste linii trebuie să conțină două numere i și j, separate prin spațiu, cu semnificația că apa din găleata cu numărul i se varsă în găleata cu numărul j.

Restricţii și precizări

• 1 ≤ n ≤ 100 000
• 1 ≤ e ≤ 5 000 000 000
• Se asigură că pentru datele de test există cel puțin o soluție posibilă,
• Dacă există mai multe soluții se poate afișa oricare dintre acestea.
• Punctajul maxim al problemei este de 100 de puncte dintre care 10 puncte din oficiu.
• Pentru teste in valoare de 18 puncte datele de intrare sunt cunoscute. Mai precis:
  Testul 0 : n = 91, e = 90
  Testul 1 : n = 30, e = 435
  Testul 2 : n = 7, e = 16
• Pentru alte teste in valoare de 15 puncte n≤9.

Exemplu

galeti.in

4 4

galeti.out

2 1
4 3
3 1

Explicații

Initial fiecare galeata contine câte un litru de apă.
1 1 1 1.
Prima dată vărsăm un litru de apa din găleata 2 în găleata 1 cu efort 1 =>
2 0 1 1.
Apoi vărsăm un litru de apă din găleata 4 în găleata 3 cu efort 1 =>
2 0 2 0.
În final vărsăm cei doi litri de apă din găleata 3 în găleata 1 cu efort 2 =>
4 0 0 0
O altă variantă corectă ar fi fost:
4 3
2 1
3 1
Observați că următoarea succesiune de vărsări este greșită:
4 2
2 1
3 1
Deși efortul depus este 4 si cei 4 litri ajung în prima găleata, la primul pas vărsarea unui litru de apă din găleata 4 în găleata 2 nu este permisă deoarece între acestea se găsește găleata 3 care conține apă.