달력

시간 제한1초메모리 제한512 MB

요약

n개 원소를 k칸 순환 회전시키는 데 필요한 구간 뒤집기 명령의 최소 개수와 그 명령들을 구한다.

난이도: 보통10점 중 7점
유형: 배열, 수학, 구현, 분할 정복
정답자: 아직 제출이 없습니다

문제

Handy Smurf는 최신 발명품인 나노봇 달력을 만들었다. 이 달력은 현재 날짜를 표시하는 나노봇들로 이루어져 있다. 날짜를 바꾸기 위해 나노봇들은 매일 $k$ 칸의 순환 회전을 수행해야 한다. 즉, 처음에 위치 $i$ 에 있던 나노봇은 이제 위치 $(i+k) \bmod n$ 에 있게 된다. 나노봇의 번호는 $0$ 부터 시작한다. 그러나 나노봇들은 단 하나의 명령만 이해할 수 있다. reverse $l$ $r$ 은 위치 $l$ 과 $r$ 사이에 있는 모든 나노봇의 위치를 뒤집는다. 즉, 처음에 위치 $l$ 에 있던 나노봇은 이제 $r$ 에, $l+1$ 에 있던 나노봇은 이제 $r-1$ 에 있게 되는 식이다. Handy가 최소 개수의 명령으로 날짜를 갱신하는 알고리즘을 작성할 수 있도록 도와주자.

입력

첫 번째 줄이자 유일한 입력 줄에는 두 정수 $n$ 과 $k$ 가 주어진다. ( $1 \leq n \leq 10^9$ , $0 \leq k < n$ ) $n$ 은 나노봇의 수, $k$ 는 회전할 칸 수를 나타낸다.

출력

출력의 첫 줄에는 사용한 reverse 명령의 수 $m$ 을 출력한다. 다음 $m$ 개의 각 줄에는 두 정수 $a$ 와 $b$ 를 출력한다. ( $0 \leq a \leq b < n$ ) 이는 다음 명령이 reverse $a$ $b$ 임을 의미한다.

예제1

예제 1
입력
```
2 1
```
예상 출력
```
1
0 1
```