[알고리즘]acm icpc 부류의 문제-4 인형

문제 설명

승연이의 취미는 인형 모으기이다. 이 사실을 알게 된 그녀의 친구들은 그녀에게 많은 인형을 선물했고, 그러다 보니 같은 종류의 인형이 여러 개 생기게 되었다. 고민 끝에 그녀는 인형들 중 m개를 골라서 자선단체에 기부하기로 했다.

그녀는 다양한 종류의 인형을 기부하는 것이 좋으리라 생각했기 때문에 아래와 같은 방법으로 기부할 인형을 골라내기로 했다. 편의상 인형의 종류를 1부터 n까지의 번호로 나타내기로 하자.

먼저 1번 인형을 한 개 고른다. 다음으로는 2번 인형을 한 개 고르고, 그 다음에는 3번 인형을 한 개 고르며, ..., 마지막으로 n번 인형을 고른다. 그리고 다시 1번 인형부터 n번 인형까지를 차례대로 한 개씩 고른다. 이 과정을 골라낸 인형의 개수가 m개가 될 때까지 반복한다. i번 인형을 고르려 했을 때, 만약 i번 인형이 더이상 남아있지 않다면 그 인형은 고르지 않고 넘어간다.

승연이가 가지고 있는 각 인형의 개수가 주어졌을 때, 각각의 인형을 몇 개씩 기부하는지 알아내는 프로그램을 작성하시오.

입력 설명

입력의 첫째 줄에는 데이터의 개수 T(1 <= T <= 50)가 주어진다. 각각의 데이터는 두 줄로 표현되는데, 첫 줄에 두 정수 n(1 <= n <= 100,000), m이 주어진다. 그리고 그 다음 줄에는 1번부터 n번까지의 인형의 개수가 차례대로 주어진다. 인형의 개수 및 m은 모두 자연수이며, 32-bit signed integer로 표현 가능한 범위 내에서 주어진다. 인형의 총 개수도 32-bit signed integer로 표현 가능한 범위에서 주어진다.

출력 설명

각각의 데이터에 대해서, 1번부터 n번까지의 인형을 각각 몇 개씩 기부하는지를 차례대로 한 줄에 출력한다.

예제 입력

5
3 3
1 5 2
3 4
1 5 2
3 5
1 5 2
3 6
1 5 2
3 7
1 5 2

예제 출력

1 1 1
1 2 1
1 2 2
1 3 2
1 4 2