Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Expression Evaluation Error

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOn the board, Bob wrote $$$n$$$ positive integers in base $$$10$$$ with sum $$$s$$$ (i. e. in decimal numeral system). Alice sees the board, but accidentally interprets the numbers on the board as base-$$$11$$$ integers and adds them up (in base $$$11$$$).

What numbers should Bob write on the board, so Alice's sum is as large as possible?

Input

The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$s$$$ and $$$n$$$ ($$$1 \leq s \leq 10^9$$$; $$$1 \leq n \leq \min(100, s)$$$) — the sum and amount of numbers on the board, respectively. Numbers $$$s$$$ and $$$n$$$ are given in decimal notation (base $$$10$$$).

Output

For each test case, output $$$n$$$ positive integers — the numbers Bob should write on the board, so Alice's sum is as large as possible. If there are multiple answers, print any of them.

Example

Input

6 97 2 17 1 111 4 100 2 10 9 999999 3

Output

70 27 17 3 4 100 4 10 90 1 1 2 1 1 1 1 1 1 999900 90 9

Note

In the first test case, $$$70_{10} + 27_{10} = 97_{10}$$$, and Alice's sum is $$$$$$70_{11} + 27_{11} = 97_{11} = 9 \cdot 11 + 7 = 106_{10}.$$$$$$ (Here $$$x_b$$$ represents the number $$$x$$$ in base $$$b$$$.) It can be shown that it is impossible for Alice to get a larger sum than $$$106_{10}$$$.

In the second test case, Bob can only write a single number on the board, so he must write $$$17$$$.

In the third test case, $$$3_{10} + 4_{10} + 100_{10} + 4_{10} = 111_{10}$$$, and Alice's sum is $$$$$$3_{11} + 4_{11} + 100_{11} + 4_{11} = 110_{11} = 1 \cdot 11^2 + 1 \cdot 11 = 132_{10}.$$$$$$ It can be shown that it is impossible for Alice to get a larger sum than $$$132_{10}$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/03/2021 23:02:12 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|