150. Mr. Beetle II

time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output

There is a small beetle living on infinite checkered sheet. Size of each cell is 1x1, the axes of Cartesian coordinate system are lying on the border of cells. Early in the morning beetle travels from his house at point (x1,y1) to the point (x2,y2). All cells that he passed are numbered in order of passing (borders and corners of cells are not considered to be parts of cells). You need to find coordinates of left lower corner of n-th cell on the way of Mr Beetle.

Input consists of integers x1,y1,x2,y2,n (1<=n<=10^5) written in one line. All coordinates are not greater than 10^6 by it's absolute values.

Write two numbers, separated by space: coordinates of left most lower point of n-th cell in the beetle's way. If such cell doesn't exist then write 'no solution'.

Sample test(s)

2 3 4 -1 3

3 0

Author:Michael R. Mirzayanov
Resource:Saratov Subregional School Team Contest, 2002
Date:Spring, 2002

Server time: 2017-09-24 12:42:22Online Contester Team © 2002 - 2016. All rights reserved.