주사위 굴리기

주사위, EsaRiutta, Pixabay 제공

KFFÍ의 구성원들은 보드게임 모임을 계획하고 있으며, 인터넷을 통해 함께 플레이하기에 적합한 롤플레잉 게임 시스템을 고르고 있다. Ravendice 게임 시스템이 선택되었다. 이 시스템은 현재 가장 인기 있는 롤플레잉 게임 시스템이 아니므로, 주사위 굴리기와 그 밖의 유사한 작업을 위한 자동화 시스템이 아직 만들어지지 않았다. 따라서 각 플레이어는 직접 주사위를 굴리고 그 결과를 소리 내어 알려야 한다. Atli는 게임을 진행하고 있는데, 일부 플레이어가 부정행위를 하고 있다고 의심하기 시작했고 결과가 실제로 가능한지 확인하기 위해 당신의 도움을 받고자 한다.

굴려야 할 주사위는 문자열로 주어진다. $n$d$m$는 $n$개의 $m$면체 주사위를 굴리고 그 결과를 합산해야 함을 나타낸다. 여기서 $m$면체 주사위는 $1, 2, \dots$부터 $m$까지의 결과가 나올 확률이 모두 같다. $n$와 $m$은 $0$보다 큰 임의의 정수일 수 있다. 그러나 이 문제에서는 $n$와 $m$가 $10^4$보다 작다. $n$d$m!$는 폭발 주사위'를 나타낸다. 이는 주사위에서 최댓값, 즉 $m$가 나오면 그 주사위를 다시 굴리고 그 결과를 더해야 한다는 뜻이다. 최댓값이 연속으로 나오면 이 과정은 여러 번 연속해서 일어날 수 있다. 폭발 주사위'에는 절대로 $m = 1$가 사용되지 않는다. 주사위 굴리기 문자열은 주사위 굴리기 또는 수를 $+$나 $-$로 구분하여 나열한 것이며, 맨 앞에 $-$가 올 수도 있다. 수 역시 $10^4$보다 작다. 예를 들어 3d6+1d4!-2는 육면체 주사위 세 개와 `폭발' 사면체 주사위 하나를 굴려 모든 결과를 합산한 뒤, 그 결과에서 둘을 빼야 함을 나타낸다.

배점

그룹 | 점수 | 제한

1 | 30 | 입력에 !가 없음

2 | 70 | 추가 제한 없음

첫 번째 줄에 하나의 정수 $q$ ($1 \leq q \leq 10^5$)가 주어진다. 이어서 각각 $2$개의 줄로 이루어진 $q$개의 질의가 주어진다. 각 질의의 첫 번째 줄에는 위에서 설명한 주사위 굴리기 문자열이 주어진다. 두 번째 줄에는 하나의 정수 $r$ ($-10^{18} \leq r \leq 10^{18}$)가 주어진다. 모든 주사위 굴리기 문자열의 길이의 합은 최대 $10^5$자이다.

각 질의에 대해 주사위 굴리기의 결과로 $r$를 얻을 수 있으면 Raunhaeft를, 그렇지 않으면 Svindl를 질의가 주어진 순서대로 각각 별도의 줄에 출력한다.