28465번 - 피보나치 사각형

문제

피보나치 수열은 $F_n = F_{n-1} + F_{n-2} (n > 2),ドル $F_1 = F_2 = 1$을 만족하는 수열이다.

$F_n$을 $n$번째 피보나치 수라고 하고, 이웃한 두 변의 길이가 $F_n,ドル $F_{n+1}$인 직사각형을 $n$번째 피보나치 사각형이라 한다.

승은이는 피보나치 수를 매우 좋아한다. 피보나치 수를 너무 좋아한 나머지 집안의 모든 물건들의 비율을 피보나치 수로 맞추었다.

그런 승은이의 집에는 피보나치 수로 이루어진 그림이 하나 있다. 매일 소파에 누워서 그 그림을 보는 것은 바깥에서 힘들게 일하고 돌아온 승은이의 유일한 낙이다.

여느 날과 같이 피보나치의 아름다움을 감상하던 그때 날파리 한 마리가 그림에 앉아 승은이의 휴식을 방해했다. 승은이는 순간 짜증이 났지만 문득 이런 생각이 들었다.

어떻게 하면 저 넓은 천장에 앉아 있는 작은 파리 한 마리의 위치를 피보나치 수와 관련되게 나타낼 수 있을까?

곰곰이 생각하던 승은이는 파리가 그림에 포함된 가장 작은 피보나치 사각형의 크기로 나타낼 수 있음을 알아냈다. 하지만 눈이 그렇게 좋지 않은 승은이는 그림에 있는 사각형을 구별을 잘 못한다.

이런 승은이를 도와 파리가 포함된 가장 작은 피보나치 사각형이 무엇인지 찾아주자.

승은이의 집에 있는 그림은 $n$번째 그림이다. $n$번째 그림은 $n$번째 피보나치 사각형 내부에 그려지며, $n>1$ 일 때 $n$번째 피보나치 사각형과 피보나치 사각형의 두 짧은 변을 일치하도록 공유하는 $n-1$번째 그림 두 개로 이루어진다.

그림의 가로와 세로의 길이가 각각 $a,ドル $b$ 라고 할 때, 그림의 좌표는 왼쪽 아래를 $(0,0)$ 오른쪽 위를 $(a,b)$로 둘 수 있다.

예시로 아래는 그림이 5번째 피보나치 사각형일 때의 모습이다.

입력

첫 줄에 그림의 가로와 세로의 길이 $a,ドル $b$가 공백으로 구분되어 주어진다. $(1 \le a, b \le 1\ 000\ 000\ 000,ドル $a,ドル $b$는 연속된 피보나치 수로 이루어져 있다.$)$

둘째 줄에 파리가 들어 있고 모든 꼭짓점의 모든 좌표가 정수인 가장 작은 정사각형의 왼쪽 아래 꼭짓점의 좌표 $x,ドル $y$가 공백으로 구분되어 주어진다. $(0 \le x < a, 0 \le y < b)$

출력

파리가 들어있는 가장 작은 피보나치 사각형이 몇 번째 피보나치 사각형인지 출력한다.

제한

힌트