시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 78 | 21 | 19 | 29.688% |
Handy Smurf created his newest invention: nanobot calendar. It obviously consists of nanobots showing current date. Every day in order to switch current date they have to perform a cyclic rotation by $k$ places (so that nanobot that was initially at position $i$ is now at position $(i+k) \bmod n$, nanobots are indexed from $0$). However, nanobots can only understand one command: reverse
$l r$ which reverses positions of all nanobots at positions between $l$ and $r$ (so that nanobot that was initially at position $l$ is now at $r$, the one that was at $l+1$ is now at $r-1$ and so on). Help Handy write an algorithm for updating the date with minimum number of commands issued.
First and only line of input contains two integers $n$ and $k$ ($1 \leq n \leq 10^9$, $0 \leq k < n$), specifying the number of nanobots and number of places to rotate.
First line of output should contain integer $m$ -- the number of reverse
commands used. On each of the next $m$ lines output two integers $a$ and $b$ ($0 \leq a \leq b < n$) which means that the next command is reverse
$a b$.
2 1
1 0 1