Zadanie

Profesor Einschwein má na dlhej poličke množstvo kníh o fyzike, usporiadané pekne podľa dátumu. Najnovšie knihy má na konci pri kuchyni, aby ich mal vždy poruke, keď si niečo potrebuje rýchlo pozrieť pri obede. Staré knihy má na vzdialenejšom konci police, ale len málokedy do nich pozerá.

Po nedávnom objavení gravitačných vĺn, sa však fyzika minulého storočia, kedy vznikla teória relativity, stala pre profesora Einschweina oveľa dôležitejšou, zatiaľ čo moderná fyzika je pre neho teraz nezaujímavá. Preto potrebuje knihy na svojej polici trochu preusporiadať.

Aby sa zachoval poriadok, chce presunúť posledných \(k\) kníh (tie čo boli blízko kuchyne) na začiatok police a zvyšné knihy posunúť o \(k\) pozícii bližšie ku kuchyni.

Presúvanie kníh je však príliš náročné, jediné čo vie Einschwein spraviť jednoducho, je vybrať niekoľko susediacich kníh a vložiť ich naspäť naopak.

Profesora by teraz zaujímalo, na koľko najmenej otočení je schopný dosiahnuť správne poradie kníh.

Úloha

Máme zoznam \(n\) kníh, očíslovaných \(0\) až \(n-1\). Na začiatku je kniha s číslom \(i\) na \(i\)-tej pozícii na polici. Chceme dostať \(k\)-tu cyklickú rotáciu zoznamu kníh, inak povedané, chceme, aby \(i\)-ta kniha bola na pozícii \((i+k) \mod n\).

Vieme robiť len operáciu obráť interval, čiže si vieme zvoliť nejaké \(a\), \(b\), a potom presunúť knihu z pozície \(a+i\) na pozíciu \(b-i\), pre \(i \in \{0..b-a\}\).

Zistite, koľko najmenej operácii je potrebných a vypíšte aj jednu správnu postupnosť operácií.

Formát vstupu

Na prvom (a jedinom) riadku vstupu sú dve čísla \(n,k\) oddelené medzerou \((1 \leq n \leq 10^9,\ 0 \leq k < n)\) – počet kníh, a o koľko pozícií je potrebné knihy posunúť.

Formát výstupu

Prvý riadok výstupu by mal obsahovať číslo \(m\) – počet potrebných reverzov. Na každom z ďalších \(m\) riadkov vypíšte v poradí vykonávania dve čísla \(a,b\ (a \leq b)\) oddelené medzerou, reprezentujúce reverz intervalu \(\left\langle a, b\right\rangle\).

Príklad

Input:

2 1

Output:

1
0 1

Toto bola jedna z ľahších úloh.

Všimnime si, že sa posun o \(k\) dá vždy spraviť na tri obrátenia intervalu. Najprv obrátime knihy na pozíciách \(1\) až \(k\), potom knihy \(k+1\) až \(n\) a napokon \(1\) až \(n\).

Ostáva teda zistiť, kedy sa to dá na menej, čiže kedy je odpoveď \(0\), \(1\) alebo \(2\). Odpoveď je \(0\) práve vtedy, keď \(k\) je 0. Pokiaľ \(k\) je 1 alebo \(n-1\) alebo oboje, tak prvé, druhé alebo oboje obrátenia nemusíme robiť a odpoveď je \(1\) alebo \(2\).

Dôkaz toho, že sa to v týchto prípadoch nedá spraviť na menej obrátení, prenechávame ako jednoduché cvičenie pre čitateľa.

Časová zložitosť riešenia je konštantná.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.