Hide

Problem G
Teningakast

Languages en is
/problems/teningakast/file/statement/en/img-0001.jpg
Dice by EsaRiutta, Pixabay
The members of KFFÍ are planning a board game night and are choosing an RPG system that is suitable for remote play. The system Ravendice ends up being chosen. Being not too popular a system there’s no built in program for dice rolling they can use. Thus each player has to roll their own dice and announce their results out loud. Atli is managing the game and is starting to suspect some players are cheating. He asks for your assistance in checking whether the dice roll results are feasible.

What dice to roll is given as a string. $n$d$m$ means one should roll $n$ $m$-sided dice and sum the results. Here $m$ sided dice are equally likely to give the results $1, 2, \dots $ and up to $m$. $n$ and $m$ can be any strictly positive integers, but in this problem they will be less than $10^4$. $n$d$m!$ denotes exploding dice which means that if the highest possible result is rolled on the dice, i.e. $m$, then the dice should be rolled again and the results added together. This can happen over and over as long as the result continues to be equal to $m$. Exploding dice will never have $m = 1$. The dice string is a sequence of dice rolls and numbers with $+$ or $-$ in between, possibly with a $-$ at the front. The numbers will also be less than $10^4$. For example 3d6+1d4!-2 means you should roll three six-sided dice, one exploding four sided die, add the results together and then subtract 2 from that total.

Input

The first line contains one integer $q$ ($1 \leq q \leq 10^5$). Then there are $q$ queries, each spanning $2$ lines. The first line contains a dice string as described above. The second line contains one integer $r$ ($-10^{18} \leq r \leq 10^{18}$). The total length of all dice strings will be at most $10^5$ characters.

Output

Print Raunhaeft if the dice roll could result in $r$, print Svindl otherwise. Print the answers in the same order as the queries and print each reply on its own line.

Scoring

Group

Points

Constraints

1

30

No ! in the input

2

70

No further restrictions

Sample Input 1 Sample Output 1
5
1d12+3
15
1d4+2d6
2
-1d6+1d4
-1
1d3!
100
1d6!-1d4!
0
Raunhaeft
Svindl
Raunhaeft
Raunhaeft
Raunhaeft