Z mod X = C solution codeforces

Z mod X = C solution codeforces

You are given three positive integers aabbcc (a<b<ca<b<c). You have to find three positive integers xxyyzz such that:

xmody=a,xmody=a,
ymodz=b,ymodz=b,
zmodx=c.zmodx=c.

Here pmodqpmodq denotes the remainder from dividing pp by qq. It is possible to show that for such constraints the answer always exists.

Input

Z mod X = C solution codeforces

The input consists of multiple test cases. The first line contains a single integer tt (1t100001≤t≤10000) — the number of test cases. Description of the test cases follows.

Each test case contains a single line with three integers aabbcc (1a<b<c1081≤a<b<c≤108).

Output

For each test case output three positive integers xxyyzz (1x,y,z10181≤x,y,z≤1018) such that xmody=axmody=aymodz=bymodz=bzmodx=czmodx=c.

You can output any correct answer.

Example
input

Z mod X = C solution codeforces

Copy
4
1 3 4
127 234 421
2 7 8
59 94 388
output

Copy
12 11 4
1063 234 1484
25 23 8
2221 94 2609
Note

In the first test case:

xmody=12mod11=1;xmody=12mod11=1;
ymodz=11mod4=3;ymodz=11mod4=3;
zmodx=4mod11=4.zmodx=4mod11=4.

SOLUTION

Click here

Leave a Comment

Your email address will not be published.