In the beginning, Takahashi has A cookies, and Aoki has B cookies. They will perform the following operation alternately, starting from Takahashi:

* If the number of cookies in his hand is odd, eat one of those cookies; if the number is even, do nothing. Then, give one-half of the cookies in his hand to the other person.



Find the numbers of cookies Takahashi and Aoki respectively have after performing K operations in total.

Constraints

* 1 \leq A,B \leq 10^9
* 1 \leq K \leq 100
* A,B and K are integers.

Input

Input is given from Standard Input in the following format:


A B K


Output

Print the number of cookies Takahashi has, and the number of cookies Aoki has, in this order, after performing K operations in total.

Examples

Input

5 4 2


Output

5 3


Input

3 3 3


Output

1 3


Input

314159265 358979323 84


Output

448759046 224379523
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int a,b,k;
	cin>>a>>b>>k;
	int i;
	for(i=0;i<k;i++){
		if(i%2==0){
			if(a%2==1){
				a--;
			}
			b=b+a/2;
			a=a/2;
		}else{
			if(b%2==1){
				b--;
			}
			a=a+b/2;
			b=b/2;
		}
	}
	cout<<a<<" "<<b<<endl;
}