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
StupidGuy: 2012-07-08 09:07:14

TLE :(

Just Trying: 2012-06-27 08:40:13

Nice problem I submitted it in 0.05s :)

Aradhya: 2012-03-21 21:12:52

nice question..my c0de took 0.04s..awes0me :D

512_I: 2011-05-17 19:10:01

@Spooky: my code is running fine on ideone.com for even extreme cases but here i m getting NZEC for python 2.5. can u tell me why so plz?

Last edit: 2011-05-17 19:29:53
R@ja.... -[^_^]-: 2011-01-12 09:12:32

1-s is too less for this problem..

Sandeep Gupta: 2010-06-21 06:19:35

gettin runtime error(NZEC) in python2.5 .....please help!!!

Spooky: 2010-04-10 06:06:44

you can try ROB in tutorial...

Last edit: 2010-04-13 20:31:37

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/