바이너리 게임

시간 제한1초메모리 제한256 MB

요약

두 이진 문자열을 읽고 앞 문자 삭제와 현재 1의 개수에 따른 패리티 추가 연산을 반복해 첫 문자열을 둘째 문자열로 바꿀 수 있는지 판정합니다.

문제

준민이는 친구 재현이, 선영이와 함께 낚시를 하고 있었다. 세 시간 동안 한 마리도 잡지 못하자 지루해진 두 사람은 준민이를 놀리려고 바이너리 게임을 시작했다.

재현이와 선영이가 0과 1로만 이루어진 문자열 $a$ 와 $b$ 를 만들어 준민이에게 준다. 준민이는 $a$ 를 $b$ 로 바꾸면 이긴다. 바꿀 때는 다음 두 연산을 원하는 순서로 몇 번이든 사용할 수 있다.

$a$ 의 맨 앞 문자를 뺄 수 있다. 예를 들어 1001은 001이 된다. $a$ 가 빈 문자열이면 더 뺄 수 없다.
$a$ 의 맨 뒤에 parity( $a$ )를 붙일 수 있다. 예를 들어 1000은 10001이 된다. parity( $a$ )는 $a$ 에 들어 있는 1의 개수가 홀수면 1, 그렇지 않으면 0이다.

게임에 자신이 없는 준민이는 자기가 이길 수 있는지 물어봤다. 문자열 $a$ 와 $b$ 를 보고 준민이가 이길 수 있는지 판정하는 프로그램을 작성하시오.

첫째 줄에 문자열 $a$ , 둘째 줄에 문자열 $b$ 가 주어진다. 두 문자열은 0과 1로만 이루어지며, 각 문자열의 길이는 1 이상 1,000 이하이다.

준민이가 이길 수 있으면 VICTORY를, 아니면 DEFEAT를 출력한다.