참을 수 없는 머슥
시간 제한1초메모리 제한1024 MB
N과 K가 주어질 때 합이 N인 음이 아닌 정수 (a1,a2,b1,b2)를 찾는다. 어떤 유효한 이진 문자열 A, B에서도 영의 개수를 같게 만드는 뒤집기 선택이 존재해야 하며, 사전순으로 최소인 답을 출력한다.
문제
머슥은 문자열을 가지고 노는 것을 매우 좋아한다. 그는 먼저 네 개의 음이 아닌 정수 가 주어졌을 때, 다음 조건을 만족하는 이진 문자열 를 만든다.
- 의 길이는 이다. 단, 는 빈 문자열일 수 없다.
- 의 길이는 이다. 단, 는 빈 문자열일 수 없다.
- 와 를 이어 붙였을 때, 이어 붙인 문자열에서 은 정확히 개 존재하여야 한다.
이후 머슥은 다음 두 가지 행동을 수행한다. 어떤 문자를 뒤집는다는 것은 해당 문자가 인 경우 로, 인 경우 으로 바꾸는 것을 의미한다.
- 이진 문자열 에서 서로 다른 위치의 문자 개를 선택하여 뒤집고, 나머지 개의 문자는 그대로 둔다.
- 이진 문자열 에서 서로 다른 위치의 문자 개를 선택하여 뒤집고, 나머지 개의 문자는 그대로 둔다.
하지만 머슥은 뒤집는 방법 중 다음 조건을 만족하지 않는 방법이 존재한다면 화를 낸다.
- 문자열을 뒤집은 후 문자열 에 있는 의 개수와 문자열 에 있는 의 개수가 같아야 한다.
모그는 을 만족하는 네 개의 음이 아닌 정수를 머슥에게 줄 것이다. 다만 머슥이 화를 내면 달래기가 매우 번거롭기 때문에, 모그가 선택한 네 정수로 머슥이 어떤 문자열을 만들더라도 머슥이 화를 내지 않도록 해야 한다. 할 일이 많았던 모그를 대신해 를 찾아주자. 이 때 수열 는 사전순으로 최소여야 한다. 만약 가능한 답이 없다면 -1을 출력한다.
입력
첫째 줄에 정수 가 공백으로 구분되어 주어진다.
출력
첫째 줄에 모그가 머슥에게 줄 네 개의 음이 아닌 정수 를 공백으로 구분하여 출력한다.
만약 가능한 답이 없다면 -1을 출력한다.
힌트
이진 문자열이란, 과 로만 이루어진 문자열을 말한다. 이진 문자열의 예시로는 "", "", "", ""등이 있다.
수열 이 수열 보다 사전 순으로 앞선다는 것은 이고 인 정수 가 존재하는 것이다.