집합 식 트랜스파일

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

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

연산을 서로 도합할 수 있습니다. 예를 들어, (A|B)&~C는 $A$와 $B$ 중 하나에 속한 원소 중 $C$에는 속하지 않은 원소들만을 추린 집합입니다. 이때, 연산자 우선순위는 ~가 가장 높고, 그 다음이 &, 마지막으로 | 순입니다. 앞서 보인 식처럼 괄호를 이용해 특정 연산자의 우선순위를 높일 수도 있습니다.

그런데, 자료조사 도중 주어진 집합에 원소가 있는지 판단하는, 엄청나게 빠르게 동작하는 구현체가 있는 ‘빼버려’라는 언어를 마주합니다. ‘빼버려’는 ‘아니야’와 다른 것은 모두 같고, 다음과 같은 차이점이 있습니다.

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

은하는 ‘아니야’의 구현체를 만드는 데에 엄청나게 빠른 ‘빼버려’의 구현체를 이용할 생각을 했습니다. 그러려면 ‘아니야’의 식을 입력받아 빠른 시간 안에 다음과 같은 조건을 만족하는 ‘빼버려’의 식으로 바꾸어 주는 트랜스파일러가 필요합니다.

• 당연히, ‘아니야’의 원래 식을 동등한 ‘빼버려’의 식으로 바꾼 결과는 원래 식과 동일한 집합을 표현해야 합니다.
• ‘빼버려’에서의 맥락은 ‘아니야’에서의 맥락과 동일하므로, ‘아니야’의 원래 식을 동등한 ‘빼버려’의 식으로 바꾼 결과는 원래 식에 등장하는 집합만을 사용해야 합니다.
• 아무리 ‘빼버려’가 빠른 구현체라도, 긴 식을 처리하는 데에는 오랜 시간이 걸릴 것입니다. 따라서 ‘아니야’의 원래 식을 동등한 ‘빼버려’의 식으로 바꾼 결과는 원래 식의 길이의 $2$배를 넘어서는 안 됩니다.

은하를 도와 이 트랜스파일러를 작성합시다!

첫 줄에 올바른 ‘아니야’의 식이 주어집니다. 식은 공백 없이 주어지며, $2024$자 이하입니다.

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

첫 줄에 YES를 출력했다면, 둘째 줄에 집합 식을 출력합니다. 이 식은 공백을 포함하지 않는 올바른 ‘빼버려’의 식이어야 하며, 지문에서 설명한 조건을 만족해야 합니다.

‘아니야’와 ‘빼버려’의 BNF(Backus-Naur Form)는 다음과 같습니다. 입력으로는 ‘아니야’의 Expression이 주어지고, 여러분은 ‘빼버려’의 Expression을 출력해야 합니다. [1]은 ‘아니야’에서만, [2]는 ‘빼버려’에서만 사용 가능합니다.