Training Site
Sideways banner

Twilight Sparkle's Magical Research

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 20 megabytes
Time limit: 0.5 seconds

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.

  • Sample Input 1

    2 3 5 1
    3
    

    Sample Output 1

    149 171