50001. Vehicle

I'm a slow walker, but I never walk backwards.

Problem description

You are on an automatic vehicle. This vehicle will automatically moves to a new location every hour according to the follow rules. If you are in position $(x, y)$, then it will move in the direction decided by $\vert ax + by\vert \% 4 $. If the result is $0$, $1$, $2$, $3$, then the vehicle will go north, east, south and west. For example, if we start at $(1, 1)$ and $a$ is $3$, and $b$ is $2$, then we will go east to $(2, 1)$ in the next hour.

We will collect gold in during this traveling. The amount of gold in location $(x, y)$ is $\vert cx + dy\vert \% e$. For example, if we are in location $(1, 1)$ and $c$ is $3$, $d$ is $4$, and $e$ is $5$, then we can collect $2$ units of gold. In addition, the gold in a location is replenishable, That means if we visit the location $(1, 1)$ three times, we can collect $6$ units of gold.

The range of our traveling is limited by the fuel of the vehicle. Every hour the vehicle will consume one unit of fuel to move to a new location. The amount of fuel you start with is $F$. Note that after you move into the new location and run out of fuel, you can still collect the gold in that location. For example, if you only have $1$ unit of fuel and go from $A$ to $B$, you can collect gold from $\textbf{both}$ locations $A$ and $B$.

There are two transporters located at positions $(p, q)$ and $(r, s)$. If you move into position $(p, q)$, you will be immediately transported to $(r, s)$ $\textbf{without}$ consuming any fuel. Similarly if you move into $(r, s)$ you will go to $(p, q)$. There is $\textbf{no}$ gold in the positions where the two transporters are located. These two transporters are $\textbf{not}$ next to each other, and you will $\textbf{not}$ start traveling from any of the transporters. You will be transported even if you do not have fuel.

Your program must simulate the vehicle movement after you start from location $(x, y)$ and report the amount of gold you collected, and the position where you run stop. All numbers $a$, $b$, $c$, $d$, $e$, $x$, $y$, and $F$ are between $0$ and $100$.

Technical Specification and constraints

  • $0 \le a, b, c, d, e, x, y, F \le 100$
  • 20 pt. $p, q, r, s > 1000$. That is, you do not need to consider the transporters.
  • 80 pt. No restriction on $p$, $q$, $r$, $s$, so you might encounter the transporters.

Input Format

There are three lines in the output. The first line has the integers $a$, $b$, $c$, $d$, $e$, the second line has the integers $p$, $q$, $r$, $s$ and the last line has the integers $x$, $y$, $F$.

Output Format

The first line print the amount of gold you collected, and the second line print the position where you run out of fuel.

Sample Input 1

1 3 5 7 9
1000 1000 1002 1002
1 1 2

Sample Output

9
0 2

Sample Input 2

1 3 5 7 9
1 2 3 4
1 1 6

Sample Output 2

19
2 4

Hint

The vehicle will go like the following according to the sample input. We start from $(1, 1)$ and collect $(5 \times 1 + 7 \times 1) \% 9 = 3$ units of gold. Then we go north since $(1 \times 3 + 5 \times 7) \% 4 = 0$, which means north. That is, we go from $(1, 1)$ to $(1, 2)$. Because $(1, 2)$ has a transport, we end up in $(3, 4)$. Note that we did not get any gold at either $(1, 2)$ or $(3, 4)$. Finally we get $19$ units of gold.

Discussion