On one of the Caribbean Islands there are N tourists and you want to move them from this island to another one.
There are only two boats on this island, the first one can hold n1 tourists and cost c1 to move exactly n1 tourists from one Island to another, and the second one can hold n2 and cost c2.
The boat will not sail unless it is fully booked. Moreover, you want to minimize the total cost of moving all tourists from one island to another. You can use any boat several times.
The input may contain multiple test cases. Each test case begins with a line containing an integer N (1 ≤ N ≤ 2 * 109).
The second line contains c1 and n1, and the third line contains c2 and n2.
Here, c1, c2, n1 and n2 are all positive integers having values smaller than 2 * 109.
A test case containing a zero for N in the first line terminates the input.
For each test case in the input, print a line containing the minimum cost solution: two non-negative integers m1 and m2, where m1 is the number of times to use the first boat, and m2 is the number of times to use the second boat) if one exists.
Print "failed" otherwise. If a solution exists, you may assume that it is unique.
## Input
The input may contain multiple test cases. Each test case begins with a line containing an integer N (1 ≤ N ≤ 2 * 109). The second line contains c1 and n1, and the third line contains c2 and n2. Here, c1, c2, n1 and n2 are all positive integers having values smaller than 2 * 109. A test case containing a zero for N in the first line terminates the input.
## Output
For each test case in the input, print a line containing the minimum cost solution: two non-negative integers m1 and m2, where m1 is the number of times to use the first boat, and m2 is the number of times to use the second boat) if one exists. Print "failed" otherwise. If a solution exists, you may assume that it is unique.
[samples]
**Definitions**
Let $ N \in \mathbb{Z} $ be the number of vertices of a convex polygon, and $ Q \in \mathbb{Z} $ the number of queries.
Let $ P = (p_0, p_1, \dots, p_{N-1}) $ be the sequence of polygon vertices in counter-clockwise order, where $ p_i = (x_i, y_i) \in \mathbb{R}^2 $.
For each query $ q \in \{1, \dots, Q\} $, let $ (l, k) \in \{0, \dots, N-1\} \times \mathbb{Z}^+ $ denote:
- $ l $: index of the left endpoint of the magical base edge,
- $ r = (l + 1) \bmod N $: index of the right endpoint (since edges are consecutive in CCW order),
- $ k $: horizontal distance from the origin along the magical base (x-axis after rotation) where the vertical wand is initially placed.
**Constraints**
1. $ 3 \leq N \leq 10^5 $, $ 1 \leq Q \leq 10^5 $
2. $ -10^9 \leq x_i, y_i \leq 10^9 $ for all $ i \in \{0, \dots, N-1\} $
3. $ 1 \leq k \leq 10^9 $ for each query
4. For each query, $ k > x' $, where $ x' $ is the maximum x-coordinate of any vertex **after rotating the polygon so that edge $ (p_l, p_r) $ lies on the positive x-axis with $ p_l $ at the origin**.
**Objective**
For each query $ (l, k) $:
1. Rotate the polygon such that:
- $ p_l \mapsto (0, 0) $,
- $ p_r \mapsto (d, 0) $ for some $ d > 0 $,
- The entire polygon is rotated rigidly around $ p_l $ to align edge $ (p_l, p_r) $ with the positive x-axis.
2. Place a vertical wand at $ x = k $ in this rotated coordinate system.
3. Find all polygon edges intersected by the line $ x = k $.
4. Output the indices (in original polygon indexing) of:
- The single vertex if the wand hits a vertex (i.e., $ k $ aligns with a rotated x-coordinate of a vertex),
- Or the two endpoints of the edge intersected (in CCW order: lower-indexed vertex first, then next in CCW order).
**Note**: The wand falls counter-clockwise — meaning it sweeps upward from the base — but since it is vertical and fixed at $ x = k $, the intersection is static. The phrase "falls counter-clockwise" implies the wand is aligned perpendicular to the base and extends upward from the base; we seek its first intersection with the polygon above the base. However, given $ k > x' $, and the polygon is convex, the wand intersects exactly one edge (or possibly a vertex) above the base. The problem states the wand hits the polygon — we assume it means the first (lowest) intersection point(s) along the vertical line $ x = k $ in the rotated frame.
Thus, after rotation, compute the intersection of the vertical line $ x = k $ with the polygon boundary, and return the original indices of the intersected point(s).