Ca în mai toate poveştile, Făt-Frumos a căutat o Cosânzeană şi a găsit-o, dar tatăl ei i-a cerut să-i paveze drumul de lungime N care leagă castelele sale. Dalele cu care va pava drumul au aceeaşi lăţime (egală cu lăţimea drumului) şi lungimi numere naturale. Fiind un împărat cam sâcâit, acesta doreşte ca pavarea să se facă folosind un număr minim de dale, diferenţa de lungime între două dale vecine să nu fie mai mare ca 1, iar prima şi ultima dală să fie de lungime 1. Împăratul nu se mulţumeşte să primească de la Făt-Frumos doar un număr (numărul minim de dale necesare): el vrea şi posibilitatea de pavare cea mai mică din punct de vedere lexicografic.
Cerinţă
Cunoscând lungimea drumului, determinaţi numărul minim de dale necesare pavării şi posibilitatea de pavare cu număr minim de dale, care este cea mai mică din punct de vedere lexicografic.
Date de intrare
Prima linie a fişierului pavare1.in conţine un număr natural V. Linia a doua conţine un număr natural N ce reprezintă lungimea drumului.
Date de ieşire
Dacă V=1, în fişierul pavare1.out se va scrie, pe prima linie, doar numărul minim de dale necesare pavării.
Dacă V=2, în fişierul pavare1.out se va scrie, pe prima linie, un şir de numere separate prin câte un spaţiu, ce reprezintă soluţia de pavare a drumului, folosind un număr minim de dale, care este cea mai mică din punct de vedere lexicografic.
Restricţii
• V poate fi 1 sau 2.
• 1 ≤ N ≤ 1000 000 000
• Pentru 30% din punctaj V = 1.
• Spunem că şirul A1, A2, ..., An este mai mic din punct de vedere lexicografic decât B1, B2, ..., Bm dacă există un indice k astfel încât Ai=Bi, pentru orice i<k, iar Ak<Bk sau k>n.
Exemple
pavare1.in
pavare1.out
Explicaţii
1
7
5
Pentru drumul de lungime 7 sunt necesare 5 dale.
2
7
1 1 2 2 1
Soluţiile cu număr minim de dale sunt: 1 1 2 2 1
1 2 1 2 1
1 2 2 1 1