시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB245839527116.626%

문제

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

입력

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

출력

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

예제 입력 1

4
2 3 4 7
2 4 5 8

예제 출력 1

1 2 2 1

예제 입력 2

2
5 9
8 6

예제 출력 2

1 2

예제 입력 3

4
1 5 6 8
7 5 3 1

예제 출력 3

1 2 1 2

예제 입력 4

4
300 300 300 300
600 10 10 10

예제 출력 4

2 1 1 2

예제 입력 5

4
50 50 50 1
30 30 30 150

예제 출력 5

1 2 2 1

출처