집합 식 트랜스파일

은하는 정해진 전체집합 안에서 집합을 다룰 수 있는 "아니야"라는 언어를 생각했습니다. "아니야"에는 A부터 T까지 총 $20$개의 집합이 있고, 다음 세 연산으로 다양한 집합을 표현할 수 있습니다.

• 교집합 연산자: 두 집합에 공통으로 속한 원소만 추려 새 집합을 만듭니다. 기호는 &입니다. ($A$ 그리고 $B$에 속한 원소)
• 합집합 연산자: 두 집합 중 한쪽 이상에 속한 원소만 추려 새 집합을 만듭니다. 기호는 |입니다. ($A$ 또는 $B$에 속한 원소)
• 여집합 연산자: 집합에 속하지 않은 원소만 추려 새 집합을 만듭니다. 기호는 ~입니다. ($A$에 속하지 않은 원소)

연산은 서로 조합할 수 있습니다. 예를 들어 (A|B)&~C는 $A$와 $B$ 중 하나에 속하면서 $C$에는 속하지 않는 원소들의 집합입니다. 연산자 우선순위는 ~가 가장 높고, 그다음이 &, 마지막이 |입니다. 괄호를 쓰면 특정 연산자의 우선순위를 높일 수 있습니다.

그런데 자료 조사 도중, 주어진 집합에 원소가 속하는지 판단하는 매우 빠른 구현체가 있는 "빼버려"라는 언어를 발견했습니다. "빼버려"는 아래 차이점을 제외하면 "아니야"와 모두 같습니다.

• 여집합 연산자를 지원하지 않습니다.
• 대신 차집합 연산자를 지원합니다. 이 연산자는 두 집합 중 왼쪽에만 속한 원소를 추려 새 집합을 만듭니다. 기호는 \입니다. 즉 A\B는 $A$에는 속하고 $B$에는 속하지 않는 원소들의 집합입니다.
• "빼버려"의 연산자 우선순위는 &가 가장 높고, 그다음이 \, 마지막이 |입니다.

은하는 빠른 "빼버려" 구현체로 "아니야" 식을 처리하려고 합니다. 이를 위해서는 "아니야" 식을 입력받아 다음 조건을 만족하는 "빼버려" 식으로 바꿔 주는 트랜스파일러가 필요합니다.

• 변환한 식은 원래 식과 동일한 집합을 표현해야 합니다.
• "빼버려"의 문맥은 "아니야"와 같으므로, 변환한 식은 원래 식에 등장하는 집합만 사용해야 합니다.
• 긴 식은 처리에 오랜 시간이 걸리므로, 변환한 식의 길이는 원래 식 길이의 2배를 넘으면 안 됩니다.

은하를 도와 이 트랜스파일러를 작성해 봅시다.

첫 줄에 공백 없이 올바른 "아니야"의 식이 주어집니다. 식의 길이는 2024자 이하입니다.

첫 줄에, 주어진 "아니야" 식을 위 조건을 만족하는 "빼버려" 식으로 바꿀 수 있으면 YES를, 그렇지 않으면 NO를 출력합니다.

YES를 출력했다면 둘째 줄에 집합 식을 출력합니다. 이 식은 공백이 없는 올바른 "빼버려" 식이어야 하며, 위 조건을 만족해야 합니다.

"아니야"와 "빼버려"의 BNF는 다음과 같습니다. 입력으로 "아니야"의 Expression이 주어지면, 여러분은 "빼버려"의 Expression을 출력해야 합니다. [1]이 붙은 규칙은 "아니야"에서만, [2]가 붙은 규칙은 "빼버려"에서만 사용할 수 있습니다.

Expression =
  | Set
  | "~" Expression            # [1]
  | Expression "&" Expression
  | Expression "\" Expression # [2]
  | Expression "\|" Expression
  | "(" Expression ")"

Set =
  | "A" | "B" | "C" | "D" | "E"
  | "F" | "G" | "H" | "I" | "J"
  | "K" | "L" | "M" | "N" | "O"
  | "P" | "Q" | "R" | "S" | "T"