Twilight Sparkle's Magical Research

While experimenting with her spells, Twilight Sparkle noticed something peculiar: she would often end up with more ingredients than she started with.

For example, if she casts the Boulanger spell on $u$ ukuleles and $v$ vuvuzelas, she would end up with $2u + 3v$ ukuleles and $5u + v$ vuvuzelas afterward.

This effect can stack: if she casts Boulanger again, she'll have $2(2u + 3v) + 3(5u + v) = 19u + 9v$ ukuleles and $5(2u + 3v) + (5u + v) = 15u + 16v$ vuvuzelas.

In general, a spell can transform $u$ ukuleles and $v$ vuvuzelas into $Au + Bv$ ukuleles and $Cu + Dv$ vuvuzelas, where $A$, $B$, $C$, and $D$ are constants specific to the spell.

Help Twilight figure out how many ukuleles and vuvuzelas she would have, given the specification for a spell and the number of times she casts it. Assume that she starts with 1 ukulele and 1 vuvuzela. (Whether that is a good idea or not is out of scope for this task.)

Input

The first line will contain four space-separated integers, $0 \le A, B, C, D < 10^4$, which specify the spell.

The second line will contain one integer, $0 \le N < 10^9$. This is the number of times Twilight wants to cast the spell.

Output

Output two space-separated integers: the final number of ukuleles and vuvuzelas, respectively.

As these numbers can be large, you must only output the last 4 digits of each number. For example, if the answer is 987654321, output 4321 instead.

Subtasks

• Subtask 1 (25%): $N \le 1000$, and the final number of ukuleles and vuvuzelas is below $10^4$.
• Subtask 2 (25%): $N \le 10^5$.
• Subtask 3 (50%): No restrictions.

Sample Explanation

Twilight Sparkle starts with 1 ukulele and 1 vuvuzela.

After casting the spell once, she has $2 \cdot 1 + 3 \cdot 1 = 5$ ukuleles and $5 \cdot 1 + 1 \cdot 1 = 6$ vuvuzelas.

After casting the spell twice, she has $2 \cdot 5 + 3 \cdot 6 = 28$ ukuleles and $5 \cdot 5 + 1 \cdot 6 = 31$ vuvuzelas.

After casting the spell three times, she has $2 \cdot 28 + 3 \cdot 31 = 149$ ukuleles and $5 \cdot 28 + 1 \cdot 31 = 171$ vuvuzelas.