시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 346 43 31 12.653%

문제

팀원의 수가 서로 같은 팀을 만드려고 하는 두 명의 대장이 있다. 선수는 현재 N명이 있고, 두 팀장은 각 선수에게 자기 나름대로의 점수를 매겼다. 각 팀의 점수는 그 팀의 팀장이 자신의 팀원에게 매긴 점수의 합이다. 모든 선수는 두 팀 중 하나에 속해야 하고, 이제 두 팀의 점수의 차이가 최소가 되게 팀을 나눠야 한다. 각 선수가 무슨 팀에 속해야 두 팀의 점수의 차이가 최소가 되는지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 선수의 수 N이 주어진다. N은 2보다 크거나 같고, 36보다 작거나 같은 짝수이다. 둘째 줄에는 팀장1이 각 선수에게 매긴 점수가 주어지고, 셋째 줄에는 팀장2가 각 선수에게 매긴 점수가 주어진다. 모든 점수는 10^15보다 작거나 같은 자연수이다.

출력

첫째 줄에 선수1부터 각 선수가 어떤 팀에 속해야 하는지 출력한다. 팀장1의 팀이 팀 1이며, 팀장2의 팀이 팀 2이다. 만약 그러한 것이 여러 개라면 사전순으로 앞서는 것을 출력한다.

예제 입력

4
2 3 4 7
2 4 5 8

예제 출력

1 2 2 1

힌트

출처