SAT (충족 가능성 문제)는 어떠한 변수들로 이루어진 논리식이 주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지를 찾는 문제이다.

스트링으로 구성된 논리식이 주어졌을 때, 변수에 적절한 값을 대입하면 참이 될 수 있을지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 논리식을 나타내는 스트링이 주어진다. (스트링의 길이 ≤ 1000)

논리식의 기본적인 정의는 아래와 같다.

• x : 변수를 나타낸다. (변수는 a~o까지 15개)
• ~x : 논리 부정(NOT)을 나타낸다. 참이면 거짓을, 거짓이면 참을 반환한다.
• x1&x2 : 논리곱(AND)을 나타낸다. x1과 x2  모두 참이면 참을, 나머지 경우는 거짓을 반환한다.
• x1|x2 : 논리합(OR)를 나타낸다. x1과 x2  둘 중 하나라도 참이면 참을, 둘 다 거짓이라면 거짓을 반환한다.
• 연산자 우선순위는 괄호로 구분된다.

틀린 논리식은 주어지지 않는다.

출력

• 변수들에 적절한 값을 대입해서 참이 나온다면
  • 첫째 줄에 1을 출력하고
  • 둘째 줄에 a부터 o까지 변수들의 값(참이면 1, 거짓이면 0)을 공백으로 구분하여 출력한다.
    단, 여러 가지 경우가 나온다면 사전순으로 빠른 것을 출력한다.

    이 문제에서 'A가 B보다 사전순으로 빠르다'는 것은, A를 뒤집어서 이진수로 나타낸 값이 B를 뒤집어서 이진수로 나타낸 값보다 작다는 것입니다.

• 참이 나오지 않는다면
  • 첫째 줄에 0을 출력한다.

입출력 예

입력

(a|(b&c))|(c&~c)

출력

1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

입력

(a|(b&c))&(c&~c)

출력

0

예제 해설

(a|(b&c)) : a가 참이거나 b,c 모두가 참이거나 a,b,c 모두가 참이면 참이 된다. 사전순으로 빠르게 하려면 a가 참이어야 한다.

(c&~c) : c가 참이든 거짓이든 항상 거짓이 된다.

출제:tncks0121