교환 비율

돈으로 물건과 서비스의 값을 치르면 대개 생활이 편리하지만, 때로는 돈을 주고받지 않고 물건을 직접 맞바꾸는 쪽을 선호하는 사람들도 있다. 일관된 "값"을 유지하기 위해 교환하는 사람들은 물건 사이의 교환 비율을 정한다.

두 물건 A와 B 사이의 교환 비율은 두 양의 정수 $m$과 $n$으로 나타내며, 물건 A $m$개가 물건 B $n$개와 같은 가치를 가진다는 뜻이다. 예를 들어 난로 2개가 냉장고 3개의 가치와 같을 수 있다. (수학적으로는 난로 1개가 냉장고 1.5개의 가치를 가지지만, 냉장고 반 개를 구하기는 어려우므로 교환 비율은 항상 정수로 나타낸다.)

여러 개의 교환 비율이 주어질 때, 임의의 두 물건 사이의 교환 비율을 계산하는 프로그램을 작성하시오.

입력은 하나 이상의 명령으로 이루어지며, 마침표(.)로 시작하는 줄이 나오면 입력이 끝난다. 각 명령은 한 줄에 하나씩 주어지며, 단언(assertion) 또는 질의(query) 중 하나이다.

단언은 느낌표(!)로 시작하고 다음 형식을 가진다.

! m itema = n itemb

여기서 itema와 itemb는 서로 다른 물건의 이름이고, $m$과 $n$은 모두 100보다 작은 양의 정수이다. 이 명령은 itema $m$개가 itemb $n$개의 가치와 같다는 뜻이다.

질의는 물음표(?)로 시작하고 다음 형식을 가진다.

? itema = itemb

이는 itema와 itemb 사이의 교환 비율을 묻는다. itema와 itemb는 서로 다른 물건이며, 둘 다 앞선 단언들에 (반드시 같은 단언은 아니더라도) 등장한 적이 있다.

각 질의에 대해, 그 시점까지 주어진 모든 단언을 바탕으로 itema와 itemb 사이의 교환 비율을 출력한다. 교환 비율은 정수여야 하며, 더 이상 약분되지 않는 기약 분수 형태로 나타내야 한다. 출력 형식은 다음과 같다.

m itema = n itemb

만약 그 시점에 교환 비율을 결정할 수 없다면, 정수 대신 물음표를 사용하여 다음과 같이 출력한다.

? itema = ? itemb

• 물건 이름의 길이는 최대 20이며, 소문자 알파벳으로만 이루어진다.
• 물건 이름은 단수형만 사용한다(복수형 없음).
• 서로 다른 물건은 최대 60종류이다.
• 서로 다른 두 물건의 어떤 쌍에 대해서도 단언은 최대 한 번만 주어진다.
• 서로 모순되는 단언은 주어지지 않는다. 예를 들어 "2 pig = 1 cow", "2 cow = 1 horse", "2 horse = 3 pig"는 서로 모순이다.
• 단언이 반드시 기약 분수 형태로 주어지지는 않지만, 출력은 반드시 기약 분수여야 한다.
• 단언에는 100보다 작은 수만 쓰이지만, 질의의 결과는 더 커질 수 있으며 기약 분수로 나타냈을 때 10000을 넘지 않는다.