역공학

경찰이 무정부주의 단체 MCA와 MBI가 주고받던 소스 코드 조각을 최근 가로챘다. 그 조각은 아래와 같다. 무정부주의자는 원칙적으로 C만 쓰기 때문에 원본은 C이고, 읽기 편하도록 Pascal로 옮긴 것도 함께 싣는다.

int main()
{ int u,v,k,t ;
  scanf("%d %d",&u,&v) ;
  for (k=0;!(u%2)&&!(v%2);k++)
    { u/=2 ; v/=2 ; }
  if (u%2) t=-v ; 
  else t=u/2 ;
  while(t) {
    while(!(t%2)) t/=2 ;
    if (t>0) u=t ; else v=-t ;
    t=u-v ; 
  }
  while(k-->0) u*=2 ; 
  printf("%d\n",u) ;
  return 0 ;
}

program zahada;
var u,v,k,t:integer;
begin
  readln(u,v); k:=0;
  while(u mod 2=0)and(v mod 2=0) do
    begin u:=u div 2; v:=v div 2; k:=k+1; end;
  if(u mod 2<>0) then t:=-v
  else t:=u div 2;
  while(t<>0) do begin
    while(t mod 2=0) do t:=t div 2;
    if(t>0) then u:=t else v:=-t;
    t:=u-v;
  end;
  while(k>0) do begin u:=u*2; k:=k-1; end;
  writeln(u:1);
end.

이 프로그램이 입력에서 두 수를 읽어 어떤 결과를 계산한다는 점은 한눈에 보인다. 그러나 계산 과정의 속내는 아직 밝혀내지 못했고, 그래서 입력과 출력이 어떻게 이어지는지 정확히 모른다. 편의상 이 프로그램이 구현하는 함수를 $f$라고 부르자. 정의역은 양의 정수 집합이다. 정수 $a$와 $b$를 프로그램 입력으로 주었을 때 프로그램이 출력하는 값이 $f(a, b)$이다. 프로그램이 끝나지 않거나 오류로 끝나면 그 입력에 대한 $f(a, b)$는 정의되지 않는다. 함수의 동작을 더 자세히 살피려면 역함수가 필요하다. 즉 $f(a, b)$가 미리 정해진 값과 같아지는 두 수 $a$와 $b$를 찾아야 한다.

첫 줄에 양의 정수 $Z$가 주어지고, 그 뒤로 $Z$개의 지시가 차례로 이어진다. 각 지시는 한 줄이고, 공백으로 구분된 두 정수 $N$과 $M$으로 이루어진다. $0 < N, M \le 1000000$이다.

각 지시마다 한 줄에 두 수 $U$와 $V$를 공백으로 구분해 출력한다. 두 수는 $f(U, V) = M$과 $1 \le V < U < N$을 모두 만족해야 한다. 조건을 만족하는 쌍이 여럿이면 $U$가 최대인 쌍을 출력한다. 최대인 $U$가 같은 해가 여럿이면 그중 $V$가 최대인 것을 출력한다. 조건을 만족하는 쌍이 하나도 없으면 그 줄에 Reseni neexistuje.를 출력한다.