Luigi's Calculations

Interview

Time limit1sMemory limit1024 MB

Summary

Given tire range [A, B], rim range [C, D], and divisor k, find x and y with x + y divisible by k and the largest possible sum, or report -1.

Level: Easy3 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

Luigi is good at choosing tires. Recently he asked Guido to run calculations that find the best combination of three factors: the road, the tires, and the rims.

In Luigi's calculations, the road is described by the number $k$ , the frequency of micro-bumps. The tires and rims are described by the numbers $x$ and $y$ , their toughness coefficients on Luigi's personal scale. Guido found through experiments that a combination is valid only if $x + y \equiv 0 \mod k$ . In other words, the sum of the tire and rim coefficients must be divisible by the frequency of micro-bumps.

Luigi always works at full capacity and wants the toughest tires from his store's stock. The store sells tires with any toughness coefficient from $A$ to $B$ , and rims with any coefficient from $C$ to $D$ . If several valid options exist for a given road, Luigi picks any option whose coefficient sum is maximal.

Write a program that takes $A$ , $B$ , $C$ , $D$ , and $k$ and determines which tires and which rims Luigi should sell.

Input

The only line contains five natural numbers $A, B, C, D, k$ ( $1 \le A, B, C, D, k \le 10^9$ ), the limits of the assortment and the frequency of micro-bumps on the road.

Output

Print one line with two numbers $x$ and $y$ ( $A \le x \le B$ , $C \le y \le D$ ), the answer to the problem. If no answer exists, print -1.

Examples3

Example 1
Input
```
1 10 1 7 3
```
Expected output
```
9 6
```
Example 2
Input
```
1 2 2 3 7
```
Expected output
```
-1
```
Example 3
Input
```
1 4 2 3 2
```
Expected output
```
4 2
```