수열의 개수

주어진 N과 C에 대해 OR이 X, AND가 Y, XOR이 Z인 31비트 정수 N개 순서쌍의 수가 정확히 C가 되는 사전순 최소 (X, Y, Z)를 구하거나 존재하지 않으면 -1을 출력한다.

어려움9비트 연산조합론수학동적 계획법아직 제출이 없습니다시간 제한1초메모리 제한128 MB

문제

NN개의 수로 이루어진 수열을 생각하자. 이 수열은 아래 네 조건을 모두 만족한다.

  1. 수열의 각 수는 00 이상 23112^{31} - 1 이하의 정수이다.
  2. 수열의 모든 수를 bitwise OR 연산한 값은 XX이다.
  3. 수열의 모든 수를 bitwise AND 연산한 값은 YY이다.
  4. 수열의 모든 수를 bitwise XOR 연산한 값은 ZZ이다.

택희는 조건을 만족하는 수열을 모두 갖고 있었지만, 이사하면서 그중 일부를 잃어버렸다. XX, YY, ZZ의 값만 알아내면 수열을 다시 전부 만들 수 있다.

택희가 기억하는 것은 두 가지다. 수열의 길이가 NN이라는 것, 그리고 네 조건을 모두 만족하는 수열이 정확히 CC개라는 것이다.

XX, YY, ZZ가 어떤 값이었을지 찾아라. 수의 순서가 다르면 서로 다른 수열로 센다.

입력

첫 줄에 수열의 길이 NN과 조건을 만족하는 수열의 개수 CC가 공백으로 구분되어 주어진다. (1N1051 \le N \le 10^5, 0C10180 \le C \le 10^{18})

출력

조건을 만족하는 수열이 정확히 CC개가 되는 00 이상 23112^{31} - 1 이하의 정수 XX, YY, ZZ를 공백으로 구분해 첫 줄에 출력한다.

조건을 만족하는 (X,Y,Z)(X, Y, Z)가 여러 개라면 사전순으로 가장 앞서는 하나를 출력한다. 즉 XX가 가장 작은 것을 고르고, 그런 것이 여럿이면 그중 YY가 가장 작은 것을, 그래도 여럿이면 그중 ZZ가 가장 작은 것을 고른다.

그러한 XX, YY, ZZ가 없으면 1-1 하나만 출력한다.