Description

Xiaoming’s class has a total class fund of $n$ yuan. The students plan to use the fund to collectively buy $3$ types of items:

1. Compass, $x$ yuan each.
2. Pen, $y$ yuan each.
3. Notebook, $z$ yuan each.

Xiaoming is in charge of ordering the stationery. Let the ordered quantities of compasses, pens, and notebooks be $a, b, c$ respectively. His ordering rules, in order, are:

1. The $n$ yuan must be spent exactly, i.e. $ax+by+cz=n$.
2. Subject to the above condition, the number of complete sets should be as large as possible, i.e. the minimum of $a, b, c$ should be as large as possible.
3. Subject to the above conditions, the total number of items should be as large as possible, i.e. $a+b+c$ should be as large as possible.

Please help Xiaoming find the optimal plan that satisfies the conditions. The data guarantees that $x>y>z$. If there are multiple solutions, output the lexicographically smallest answer $(a, b, c)$.

Input Format

The input contains multiple test cases. The first line contains an integer $T$, indicating the number of test cases.

The next $T$ lines each contain four integers: the class fund $n$, and the prices $x, y, z$ of the three items.

Output Format

For each test case, if there is no solution, output $-1$.

Otherwise, output one line with three integers separated by spaces: $a, b, c$, representing the number of compasses, pens, and notebooks.

3
33 7 4 3
81 39 37 7
227200291 189101 133029 52503

1 2 6
1 0 6
446 845 580

Hint

For all testdata, $1\leq T\leq 100$, $0\leq n\leq 10^9$, $1\leq z<y<x\leq 10^9$.

Translated by ChatGPT 5