수열의 개수
시간 제한1초메모리 제한128 MB
주어진 N과 C에 대해 OR이 X, AND가 Y, XOR이 Z인 31비트 정수 N개 순서쌍의 수가 정확히 C가 되는 사전순 최소 (X, Y, Z)를 구하거나 존재하지 않으면 -1을 출력한다.
문제
개의 수로 이루어진 수열을 생각하자. 이 수열은 아래 네 조건을 모두 만족한다.
- 수열의 각 수는 이상 이하의 정수이다.
- 수열의 모든 수를 bitwise OR 연산한 값은 이다.
- 수열의 모든 수를 bitwise AND 연산한 값은 이다.
- 수열의 모든 수를 bitwise XOR 연산한 값은 이다.
택희는 조건을 만족하는 수열을 모두 갖고 있었지만, 이사하면서 그중 일부를 잃어버렸다. , , 의 값만 알아내면 수열을 다시 전부 만들 수 있다.
택희가 기억하는 것은 두 가지다. 수열의 길이가 이라는 것, 그리고 네 조건을 모두 만족하는 수열이 정확히 개라는 것이다.
, , 가 어떤 값이었을지 찾아라. 수의 순서가 다르면 서로 다른 수열로 센다.
입력
첫 줄에 수열의 길이 과 조건을 만족하는 수열의 개수 가 공백으로 구분되어 주어진다. (, )
출력
조건을 만족하는 수열이 정확히 개가 되는 이상 이하의 정수 , , 를 공백으로 구분해 첫 줄에 출력한다.
조건을 만족하는 가 여러 개라면 사전순으로 가장 앞서는 하나를 출력한다. 즉 가 가장 작은 것을 고르고, 그런 것이 여럿이면 그중 가 가장 작은 것을, 그래도 여럿이면 그중 가 가장 작은 것을 고른다.
그러한 , , 가 없으면 하나만 출력한다.