어려운 리팩터링

비교식으로 주어진 정수 구간들의 합집합을 병합한 뒤, 상수 개수가 최소가 되도록 다시 출력한다. 끝이 -32768이나 32767인 구간과 항상 참, 항상 거짓인 경우를 따로 처리한다.

보통6구간정렬구현수학면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

헬렌은 "마법 상수"를 잔뜩 쓰는 코드를 발견했다. 그 안에는 정수 x가 어떤 구간들의 합집합에 속하는지 검사하는 논리식이 있었다. 예를 들면 이런 모습이다.

x >= 5 && x <= 10 ||
x >= 7 && x <= 20 ||
x <= 2 ||
x >= 21 && x <= 25 ||
x >= 8 && x <= 10 ||
x >= 100

헬렌은 마법 상수를 싫어해서 이 식과 비슷한 식을 모두 리팩터링하기로 했다. 리팩터링한 식은 모든 정수 x에 대해 원래 식과 참거짓 값이 같으면서, 식 안에 적힌 정수 상수의 개수가 가능한 한 적어야 한다.

이 문제에 나오는 모든 정수는 x를 포함해 부호 있는 16비트 정수 범위에 들어간다. 즉 215=32768-2^{15} = -32768 이상 2151=327672^{15} - 1 = 32767 이하다.

입력

입력은 1개 이상 1000개 이하의 줄로 이루어진다. 각 줄은 비교식 하나이거나, 논리곱 연산자 &&로 이어진 비교식 두 개다. 비교식은 x로 시작하고, 그다음에 크거나 같음 연산자 >= 또는 작거나 같음 연산자 <=가 오고, 마지막에 정수 상수가 온다. 한 줄에 비교식이 두 개 있으면 앞쪽은 항상 >=이고 뒤쪽은 <=다.

마지막 줄을 뺀 모든 줄은 논리합 연산자 ||로 끝난다. 한 줄의 토큰은 공백 한 칸으로 구분되고, 줄 앞뒤에 공백은 없다.

출력

리팩터링한 식을 입력과 같은 형식으로 출력한다. 출력한 식은 모든 정수 x에 대해 원래 식과 참거짓 값이 같아야 하고, 식에 적힌 정수 상수의 개수가 최소여야 한다.

상수 개수가 최소인 식은 여러 가지로 적을 수 있으므로, 출력 형태를 다음과 같이 고정한다.

  • 원래 식이 참이 되는 x의 집합을 서로 떨어진 최대 구간들로 나눈다.
  • 각 최대 구간을 한 줄로 쓰고, 왼쪽 끝이 작은 구간부터 오름차순으로 출력한다.
  • 하한이 32768-32768인 구간 [32768,b][-32768, b]x <= b로 쓴다.
  • 상한이 3276732767인 구간 [a,32767][a, 32767]x >= a로 쓴다.
  • 그 밖의 구간 [a,b][a, b]x >= a && x <= b로 쓴다.
  • 마지막 줄을 뺀 모든 줄은 ||로 끝낸다.

상수는 앞에 0을 붙이지 않고 쓰고, 한 줄의 토큰 사이에는 공백을 정확히 한 칸만 둔다.

식이 모든 정수 x에 대해 참이면 true만 한 줄에 출력한다. 모든 정수 x에 대해 거짓이면 false만 한 줄에 출력한다.