중간계에 전쟁이 일어나려고 한다. 간달프는 사우론에 대항하기 위한 군대를 소집했고, 여러 종족이 이 군대에 가담했다. 전쟁을 시작하기 전에 간달프는 각 종족에 점수를 매겼다.

간달프의 군대의 각 종족의 점수는 다음과 같다.

• 호빗 - 1
• 인간 - 2
• 엘프 - 3
• 드워프 - 3
• 독수리 - 4
• 마법사 - 10

사우론의 군대의 점수는 다음과 같다.

• 오크 - 1
• 인간 - 2
• 워그(늑대) - 2
• 고블린 - 2
• 우럭하이 - 3
• 트롤 - 5
• 마법사 - 10

중간계는 매우 신비한 곳이어서 각 전투의 승리는 날씨, 장소, 용맹에 영향을 받지 않는다. 전투에 참여한 각 종족의 점수를 합한 뒤, 큰 쪽이 이긴다.

전투에 참여한 종족의 수가 주어졌을 때, 어느 쪽이 이기는지 구하는 프로그램을 작성하시오.

첫째 줄에 전투의 개수 T가 주어진다. 각 전투는 두 줄로 이루어져 있다. 첫째 줄에 간달프 군대에 참여한 종족의 수가 주어진다. 이 값은 공백으로 구분되어 있으며, 호빗, 인간, 엘프, 드워프, 독수리, 마법사 순서이다. 둘째 줄에는 사우론 군대에 참여한 종족의 수가 주어진다. 이 값 역시 공백으로 구분되어 있으며, 오크, 인간, 워그, 고블린, 우럭하이, 트롤, 마법사 순서이다. 모든 값은 음이 아닌 정수이고, 각 군대의 점수의 합은 32비트 정수 제한을 넘지 않는다.

각 전투에 대해서, "Battle"과 전투 번호를 출력한다. 그 다음에 간달프의 군대가 이긴다면 "Good triumphs over Evil"를, 사우론의 군대가 이긴다면 "Evil eradicates all trace of Good", 점수의 합이 같아 이기는 쪽이 없다면 "No victor on this battle field"를 출력한다.

야바위를 잘하는 재열이는 축제기간동안 홍문관 앞에 부스를 열어 돈을 벌어보려 한다. 

재열이는 컵 네 개를 일렬로 탁자 위에 올려놓고, 가장 왼쪽 컵에 작은 공 하나, 가장 오른쪽 컵에 큰 공 하나를 넣어놓았다. 이제 재열이는 컵 2개의 위치를 바꿔가면서 여러번 섞을 것이고, 모두 섞은 뒤에 상대방에게 어떤 컵에 공이 들어있는지 말하라고 할 것이다. 컵이 4개가 있을 때, 위치를 바꿀 수 있는 가능한 방법은 아래와 같이 6가지가 있다.

떼돈을 벌기 위해 3개월을 연습한 재열이에게 내기를 이길 수 있는 사람은 거의 없다.  그러나, 마침 엄청난 동체시력의 보유자 영범이 홍문관 앞을 지나고 있었다.  영범은 내기를 제안하고, 아무것도 모르는 재열이는 말없이 컵을 섞기 시작한다.  재열이의 손놀림이 아무리 빠르더라도, 영범이의 동체시력을 속일 수는 없다. 영범이는 동체시력뿐만 아니라, 기억력도 뛰어나서 재열이가 컵을 섞은 순서를 다 기억할 수 있다.  이것을 모르는 재열이의 운명은 당신이 작성할 프로그램에 달려있다.

재열이가 컵을 섞은 방법이 순서대로 주어질 때, 어떤 컵에 작은 공이 있는지, 어떤 컵에 큰 공이 있는지 차례대로 출력하는 프로그램을 작성하시오. 

첫째 줄에 재열이가 컵을 섞는 순서가 주어진다. 이 순서는 위 그림에 있는 A, B, C, D, E, F 중 하나이다. 재열이는 컵을 최대 200번 섞는다.

첫번째 줄에는 작은 공이 있는 위치를, 두번째 줄에는 큰 공이 있는 위치를 출력한다. 공의 위치는 가장 왼쪽부터 1, 2, 3, 4로 표시한다.  

홍익대학교 근처에 있는 오락실에 새로운 게임이 들어왔다. 이 게임을 클리어하려면 방금 막 금은방을 턴 마포구 대도 X가 되어 아무에게도 들키지 않고 X의 집에 무사히 도착해야 한다. 게임은 오직 좌우 버튼 두 개로만 진행되고 규칙은 아래와 같다.

1. 마포구의 모든 건물은 일렬로 나열되어 있고 각 건물에는 1번부터 N번까지 번호가 지정되어 있다. 마포구에는 K개의 경찰서가 있고 경찰 내부에는 이미 X의 얼굴이 알려졌다.
2. 게임이 시작될 때 X는 막 범행을 끝내고 금은방 S에 있다.
3. X는 자신의 집 D에 마포구를 떠날 수 있는 비밀 통로를 만들어놓았다. 따라서 경찰에게 발각되지 않고 무사히 집으로 돌아가야 한다.
4. 좌(←) 버튼을 누르면 후방으로, 우(→) 버튼을 누르면 전방으로 이동한다. X는 마포구 내에서만 이동할 수 있으며, 자신이 오랜 연구 끝에 알아낸 이동 방식을 맹신하여 오직 그 방식으로만 이동한다.
5. X의 달리기는 매우 빨라서 전방으로 F개의 건물, 후방으로 B개의 건물을 얼굴이 보이지 않는 빠르기로 달릴 수 있다. 하지만 자신도 주체할 수 없을 만큼 빨라서 중간에 멈출 수 없으며, 한 번 달리면 너무 힘들어 10초 동안 건물 앞에서 휴식을 취해야 한다.
6. X가 경찰서 앞에서 휴식을 취할 경우 그는 집에 돌아가지 못하고 체포된다.

이 게임은 아직 베타 버전이라 무사히 집으로 가는 방법이 없는 버그도 존재한다.

지언이의 취미는 오락실 게임을 누구보다 빠르게 클리어하는 것이다. 그래서 대도 X가 무사히 집에 도착할 수 있는 여러 방법 중에서도 좌우 버튼을 가장 최소로 눌렀을 때의 횟수를 알고 싶다.

마포구 건물의 개수 N, 털린 금은방 S, 빈집털이범의 집 D, 앞으로 한 번에 달릴 수 있는 건물 수 F, 뒤로 한 번에 달릴 수 있는 건물 수 B, 마포구 경찰서의 개수 K, 각 경찰서의 건물 번호 l1, l2, …, lK가 주어질 때 대도 X가 무사히 집에 도착하기 위해 버튼을 눌러야 하는 최소 횟수를 출력하는 프로그램을 작성해라.

만약 집으로 가는 방법이 없는 경우를 발견했다면 이 데이터를 게임 회사에 알리기 위해 “BUG FOUND”를 출력한다.

첫째 줄에 N, S, D, F, B, K가 주어지고, K > 0인 경우에는 둘째 줄에 경찰서의 위치 l1, l2, …, lK가 주어진다. (1 ≤ S, D, k ≤ N ≤ 100000, 0 ≤ F, B ≤ 100000, 0 ≤ K ≤ N/2, S ≠ D ≠ l) 

첫째 줄에 대도 X가 건물 S에서 자신의 집 D로 무사히 가기 위해 지언이가 버튼을 눌러야 하는 최소 횟수를 출력한다. 만약, D에 도달할 수 없는 데이터인 경우 “BUG FOUND”를 출력한다.

문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때,

1. 0 ≤ Ai < 225 = 33554432, i=1,2,…,N.
2. 입력의 갯수 N은 1 이상 500만 이하이다.

첫째 줄에 A1, A2, ..., AN이 주어진다.

B1, B2, ..., BN’을 출력한다.

메모리 제한에 유의하시오.

영식이는 숫자를 셀 때, 왼손을 이용한다. 엄지손가락부터 시작해서 새끼손가락까지 차례대로 하나씩 센다. 그다음에 새끼손가락까지 센 다음에는 반대로 엄지손가락으로 다시 역방향으로 센다. 영식이는 자기가 원하는 숫자가 나올 때 까지 계속해서 이 방법으로 센다. 영식이는 절대 손가락을 건너뛰지 않는다. 예를 들어 숫자 10을 셀 때는, 엄지->검지->중지->약지->새끼->약지->중지->검지->엄지->검지 이렇게 센다.

슬프게도, 영식이는 민식이와 싸우다가 손가락을 하나 다쳤다. 멍청한 영식이는 오른손으로는 셀 수 없기 때문에, 오늘도 역시 왼손으로 세야 한다. 영식이는 다친 손가락을 아얘 쓸 수 없는 것은 아니고, 셀 수 있는 횟수가 제한되어 있는 것이다.

영식이가 셀 수 있는 최대 숫자를 출력하는 프로그램을 작성하시오.

첫째 줄에 영식이가 다친 손가락이 주어진다. 엄지부터 차례대로 1,2,3,4,5로 번호가 매겨져 있다. 둘째 줄에는 영식이가 다친 손가락으로 몇 번 셀수 있는지 주어진다. 이 수는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

첫째 줄에 영식이가 셀 수 있는 수의 최대값을 출력한다. 만약 시작도 할 수 없으면 0을 출력한다.

1,2,3,4,5,4,3,2,1,2,3,4,5,4,3 위와같이 세면 총 15를 셀 수 있다. 2번째 손가락을 3번 이용했으므로 더 이상 이용할 수 없기 때문에 여기가 영식이의 한계이다.

어떠한 자연수 N에 대해서 N을 제외한 약수(진약수)의 합이 N이 되는 자연수를 완전수라고 한다. 예를 들어, 6의 약수는 1, 2, 3, 6인데 1+2+3은 6이기 때문에 완전수이다. 또 진약수의 합이 자기 자신보다 작은 경우를 부족수, 진약수의 합이 자기 자신보다 큰 경우를 과잉수라고 한다.

이 때, 어떤 수가 주어질 때 이 수가 완전수인지, 부족수인지, 과잉수인지를 구하는 프로그램을 작성하시오.

첫째 줄에 자연수의 개수 T가 주어진다. T은 1000보다 작은 수이다.

둘째 줄에는 공백을 사이에 두고 완전수인지 구해야 되는 자연수 N이 주어진다.(N<10000)

T개 줄에 걸쳐서 각 자연수에 대해서 완전수면 ‘Perfect’, 부족수면 ‘Deficient’, 과잉수면 ‘Abundant’를 출력한다.

28의 경우 약수가 1, 2, 4, 7, 14, 28 이고, 1+2+4+7+14=28이기 때문에 완전수이다.

21의 경우 약수가 1, 3, 7, 21 이고, 1+3+7=11<21이기 때문에 부족수이다.

36의 경우 약수가 1, 2, 3, 4, 6, 9, 12, 18, 36 이고, 1+2+3+4+6+9+12+18=55>36이기 때문에 과잉수 이다.

JOI시는 남북방향이 H 킬로미터, 동서방향이 W 킬로미터인 직사각형 모양이다. JOI시는 가로세로 길이가 1킬로미터인 H × W 개의 작은 구역들로 나뉘어 있다. 북쪽으로부터 i 번째, 서쪽으로부터 j 번째에 있는 구역을 (i, j) 로 표시한다.

각 구역의 하늘에는 구름이 있을 수도, 없을 수도 있다. 모든 구름은 1분이 지날 때마다 1킬로미터씩 동쪽으로 이동한다. 오늘은 날씨가 정말 좋기 때문에 JOI시의 외부에서 구름이 이동해 오는 경우는 없다.

지금 각 구역의 하늘에 구름이 있는지 없는지를 알고 있다. 기상청에서 일하고 있는 여러분은 각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 예측하는 일을 맡았다.

각 구역에 대해서 지금부터 몇 분뒤 처음으로 하늘에 구름이 오는지를 구하여라.

입력은 1 + H 행으로 주어진다.

첫 번째 행에는 정수 H, W (1 ≦ H ≦ 100, 1 ≦ W ≦ 100) 가 공백을 사이에 주고 주어진다. 이것은 JOI시가 H × W 개의 작은 구역으로 나뉘어 있다는 것을 의미한다.

이어진 H 개의 행의 i번째 행 (1 ≦ i ≦ H) 에는 W문자의 문자열이 주어진다. W 개의 문자 중 j번째 문자 (1 ≦ j ≦ W) 는, 구역 (i, j) 에 지금 구름이 떠 있는지 아닌지를 나타낸다. 구름이 있는 경우에는 영어 소문자 'c' 가, 구름이 없는 경우에는 문자 '.' 가 주어진다.

출력은 H 행으로, 각 행에는 공백으로 구분된 W 개의 정수를 출력한다. 출력의 i 번째 행 j 번째 정수 (1 ≦ i ≦ H, 1 ≦ j ≦ W) 는, 지금부터 몇 분후에 처음으로 구역 (i, j) 에 구름이 뜨는지를 표시한다. 단, 처음부터 구역 (i, j) 에 구름이 떠 있었던 경우에는 0을, 몇 분이 지나도 구름이 뜨지 않을 경우에는 -1을 출력한다.

출력되는 각 줄의 처음과 끝에 불필요한 공백을 넣지 않도록 한다.

입출력 예제 1에서는, JOI시가 3 × 4 개의 작은 구역으로 나뉘어 있다. 지금 JOI시의 구름 상황은 아래와 같다. 그림의 위쪽이 북쪽이다.

1분 간격으로 구름은 다음과 같이 움직인다.

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 갯수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 갯수를 구하는 프로그램을 작성하시오.

예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다.

입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.

제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.