Group the Numbers

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

요약

정수 1부터 n까지를 크기가 같은 k개의 그룹으로 나눌 때, 그룹 합의 최댓값과 최솟값의 차이가 최소가 되도록 배정하는 문제입니다.

난이도: 보통10점 중 7점
유형: 그리디, 수학, 정렬
정답자: 아직 제출이 없습니다

문제

Consider the set of all integers from $1$ to $n$ . Split these integers into $k$ equal-sized groups in such a way that the difference between the maximum and minimum sums of integers among all groups is minimized. Formally, if $s\_i$ is the sum of integers in $i$ -th group, the following value should be minimized:

$\max\limits\_{i=1}^k s\_i - \min\limits\_{i=1}^k s\_i\text{.}$

입력

The first line contains two integers $n$ and $k$ ( $1 \leq n, k \leq 100\\,000$ ; $n$ is divisible by $k$ ).

출력

For each group, print a line with all the integers belonging to that group. If there are multiple optimal answers, output any one of them.

예제2

예제 1
입력
```
6 2
```
예상 출력
```
1 4 5
2 3 6
```
예제 2
입력
```
12 3
```
예상 출력
```
1 7 12 6
10 3 9 4
5 2 8 11
```