공정성 관리

프로그래밍 대회에서 가장 중요한 역할 중 하나는 최고 공정 책임자(CEO, Chief Equality Officer)이다. 이 사람은 모든 팀이 우승할 기회를 똑같이 갖도록 관리한다. 작년 NWERC 이후 현재 CEO인 Gregor는 대회를 더 공정하게 만들 방법을 오래 고민했다.

그의 답은 제출에 쓸 수 있는 유일한 언어로 새 프로그래밍 언어를 도입하는 것이었다. 허용된 언어 중 하나에 익숙하지 않아서 불리해지는 팀은 없다. 이 언어의 이름은 BALLOON이며, Building A Long List Of Ordinary Numbers의 줄임말이다. 자료형은 정수 리스트 하나뿐이다. 언어를 빠르게 유지하려고 명령어는 네 개만 있다.

• [x1,...,xn]은 리스트를 만드는 생성자다. 대괄호 안의 정수를 주어진 순서대로 담아 반환한다.
• concat(<Expr1>,<Expr2>)는 <Expr1>을 계산해 나온 정수를 먼저 놓고, 그 뒤에 <Expr2>를 계산해 나온 정수를 붙여 반환한다.
• shuffle(<Expr>)는 <Expr>이 반환한 정수를 균등하게 무작위로 고른 순열로 재배열해 반환한다. 각 순열이 같은 확률로 쓰인다.
• sorted(<Expr>)는 <Expr>이 반환한 정수를 비내림차순으로 재배열해 반환한다.

예를 들어 concat(shuffle([1,2]),shuffle([1,2]))를 보자. 각 shuffle은 [1,2]를 받아 확률 $0.5$로 [1,2] 또는 [2,1]을 반환하며, 두 결과는 서로 독립이다. 바깥의 concat이 두 결과를 이어 붙이므로 [1,2,1,2], [1,2,2,1], [2,1,1,2], [2,1,2,1] 중 하나가 각각 확률 $0.25$로 나온다.

BALLOON의 출력은 확률적이므로 제출물을 바이트 단위로 비교해 채점할 수 없다. 심사 서버는 제출 프로그램이 심사위원의 기준 풀이와 동등한지 확인한다. 두 프로그램은 임의의 정수 리스트 $L$에 대해 둘 다 $L$을 반환할 확률이 같을 때 동등하다.

당신의 과제는 주어진 두 BALLOON 프로그램이 동등한지 판단하는 것이다.

입력은 다음과 같다.

• 첫 번째 프로그램 A를 담은 한 줄의 문자열.
• 두 번째 프로그램 B를 담은 한 줄의 문자열.

각 프로그램의 길이는 3자 이상 $10^6$자 이하이다. 프로그램에는 공백과 빈 리스트가 없으므로, 입력에 공백이나 []가 나타나지 않는다. 프로그램에 나오는 각 정수는 0보다 크고 $10^9$보다 작다.

두 프로그램이 동등하면 equal을, 그렇지 않으면 not equal을 출력한다.