ROBBERY2 - Robbery 2


k bandits robbed a bank. They took away n gold coins. Being a progressive group of robbers they decided to use the following procedure to divide the coins. First the most respected bandit takes 1 coin, then the second respected takes 2 coins, ..., the least respected takes k coins, then again the most respected takes k+1 coins, and so on, until one of the bandits takes the remaining coins. Calculate how much gold each of the bandits gets.

Input

The first line of the input contains number t – the amount of tests. Then t test descriptions follow. Each test consists of two integers n and k - the amount of coins and bandits respectively.

Constraints

1 <= t <= 500
106 <= n <= 1015
2 <= k <= 100

Output

For each test print the amounts of coins each bandit gets separated by spaces.

Example

Input:
3
1000000 2
1234567 3
123456789 4

Output:
499849 500151
411602 411887 411078
30869901 30858368 30862296 30866224

hide comments
viratian_070: 2017-06-18 13:32:10

great question

aman224: 2016-09-08 15:34:17

AC in one go!!!! easy prob. just use the concept of AP and its a piece of cake

coder_hsnake: 2016-08-30 22:35:32

Use QUADRATIC FORMULA nice problem

agarwalg271: 2016-08-30 14:23:00

finally accepted after 6WA by using dharacharya

Last edit: 2016-08-31 17:44:04
shubham2305: 2016-06-05 21:40:00

use unsigned long long int
otherwise expect WA

akashmandal21: 2016-05-16 22:36:20

AC in one go :)
nice ques!!

minhthai: 2016-03-06 10:35:44

hint: use unsigned long long :)

Anant Upadhyay: 2015-08-13 15:00:38

accepted in one go...:)

scyth3r: 2015-07-08 11:13:32

one of the best solution in python....obviously along with numerix :p

[Mayank Pratap]: 2015-06-13 18:23:19

When I take int k I get WA
When I take long long int k I get AC: )
Can somebody give a hint why its so ??

Last edit: 2015-06-13 18:28:17

Added by:Spooky
Date:2010-03-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Advancement Spring 2010, http://sevolymp.uuuq.com/