첫째 줄에 정수의 개수 N이 주어지고, 둘째 줄에는 N개의 자연수가 공백을 사이에 두고 차례대로 주어집니다.

입력된 N개의 자연수들을 모두 기억해 두었다가, 첫째 줄에는 입력된 순서대로 홀수들만 공백으로 구분하여 출력하고,

둘째 줄에는 입력된 순서대로 짝수들만 공백으로 구분하여 출력하는 프로그램을 작성하시오.

만약 입력된 데이터 중 홀수만 존재하거나 짝수만 존재하여 어느 한쪽의 출력 대상이 아예 없다면, 해당 줄은 아무것도 출력하지 않고 빈 줄로 둡니다.

입력

첫째 줄에 정수의 개수 N이 주어진다. 둘째 줄에는 N개의 자연수가 공백을 사이에 두고 차례대로 주어진다.

출력

첫째 줄에 입력된 홀수들을 순서대로 공백으로 구분하여 출력한다. 둘째 줄에 입력된 짝수들을 순서대로 공백으로 구분하여 출력한다.

제한 사항

• 1 ≤ N ≤ 1,000
• 입력되는 모든 수는 1 이상 10,000 이하의 자연수이다.

예제 입력 1

6
3 8 5 2 7 7

예제 출력 1

3 5 7 7
8 2

예제 입력 2

4
2 6 6 2

예제 출력 2

2 6 6 2