C1. k-LCM (easy version)-Codeforces Round ＃708 (Div. 2)

Problem - 1497C1 - Codeforces

C1. k-LCM (easy version)

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

It is the easy version of the problem. The only difference is that in this version k=3k=3.

You are given a positive integer nn. Find kk positive integers a1,a2,…,aka1,a2,…,ak, such that:

• a1+a2+…+ak=na1+a2+…+ak=n
• LCM(a1,a2,…,ak)≤n2LCM(a1,a2,…,ak)≤n2

Here LCMLCM is the least common multiple of numbers a1,a2,…,aka1,a2,…,ak.

We can show that for given constraints the answer always exists.

Input

The first line contains a single integer tt (1≤t≤104)(1≤t≤104)  — the number of test cases.

The only line of each test case contains two integers nn, kk (3≤n≤1093≤n≤109, k=3k=3).

Output

For each test case print kk positive integers a1,a2,…,aka1,a2,…,ak, for which all conditions are satisfied.

Example

input

Copy

3
3 3
8 3
14 3

output

Copy

1 1 1
4 2 2
2 6 6

====================================================================================================

把3-100的数字全部打表打出来，答案基本上就能确定了，分奇偶讨论一下，每个人的规律不一定相同，满足条件即可

# include<iostream>
# include<cstring>
# include<queue>
# include<algorithm>
# include<math.h>
using namespace std;

# define mod 1000000007

typedef long long int ll;

int main ()
{



int t;

cin>>t;

while(t--)
{


    int n;
    cin>>n;

    int k;

    cin>>k;



       if(n%3==0)
       {
           cout<<n/3<<" "<<n/3<<" "<<n/3<<endl;

       }
       else if(n%4==0)
       {
           cout<<n/2<<" "<<n/4<<" "<<n/4<<endl;

       }
       else
       {
           cout<<(n-1)/2<<" "<<(n-1)/2<<" "<<n-(n-1)/2*2<<endl;

       }




   }



    return 0;

}