Description

Background Story

You are an audience of Yu-Gi-Oh, the player, Ricky, just won the world championship. However, earthquake is coming and a giant wall is rising which is blocking Ricky’s way so that he can’t leave the place.

At that moment, Ricky wants to summon the monsters to real world then break the wall so that he can get out and receive his reward.

Simple Rule Explanation

• Ricky’s every decision is “Turn-Based”, so he will only make one decision in a turn.

• Every turn Ricky will have two decisions:

  • Summon the monsters to the real world.
    • Real World: there are two spaces for monsters real world, those are left side and right side.
    • Whenever Ricky summon a monster, he summons it at left side first, unless left side already contains a monster.
    • There can be up to two monsters(<=2) in the real world.
  • Make the monsters attack the wall.
    • Each attack contains sum of Star Points of monsters in real world.
    • For example, if this monster have 6 star points, then it will damage the wall by 6.

• If Ricky wants to summon the monster with Star Points higher than 4(Star Points > 4), then Ricky needs to sacrifice specific number of monsters. Here is the rule of summon:

  • Sacrifice: the monster which was sacrificed will leave the real world. Ricky will sacrifice the monster having the fewest star points first. If all the monsters in real world have same star points, then choose the left one. In addition, it will be summon on the same side as where you sacrifice the monster(if sacrifice two monsters, then summon at left side).
  • Monster with Star Points <= 4: Ricky can summon the monster without sacrifice any monster.
  • 5 <= Monster with Star Points <= 6: Ricky need to acrifice one monster to summon this monster.
  • 7 <= Monster with Star Points <= 8: Ricky need to sacrifice two monsters to summon this monster.
  • Ricky might sacrifice higher level monster for >=5 stars new monster

• Whenever Ricky decides to attack the wall, the damage is based on sum of the Star Points of monsters in the real world.

• In the end, you need to explain two things to your Uncle because he wants to know the outcome as well:

  • How Ricky summoned the monsters(the monster you sacrifice to summon the current monsters) by preorder traversing.
  • Sum of all damages Ricky gave to the wall.

Simple Demonstration

• The turns Ricky decides will be like:

Summon -> 4* 
//first turn Ricky summons 4 star points monster
//real world:(4*, )
//structure:
       real world
     /           \
    4*

Summon -> 3* 
//second turn, Ricky summons 3 star points monster
//real world:(4*, 3*)
//Ricky reach the number of monsters limitation in real world.
//structure:
       real world
     /           \
    4*           3*


Summon -> 5* 
//third turn, Ricky summons 5 star points monster
//sacrifice the monster with lower star points in real world first.
//in this case, Ricky will sacrifice 3* monster.
//real world:(4*,5*)
//structure:
       real world
     /           \
    4*           5*
                   \
                    3*

Attack
//fourth turn, Ricky does attack
//the wall will receive the damage from sum of star points in real world.
//(4*,5*) -> damage = 4+5 = 9

Summon -> 8*
//fifth turn, Ricky summons 8* monster which needs to sacrifice 2 monsters.
//real world:(4*,5*)->(8*, )
//structure:
       real world
     /          
    8*           
   /  \           
  4*  5*
       \
       3*

Summon -> 4*
//sixth turn, Ricky summons 4* monster
//real world:(8*,4*)
//structure:
       real world
     /           \
    8*            4*
   /  \           
  4*  5*
       \
       3*


Attack
//seventh turn, Ricky does attack
//(8*,4*) -> damage = 8+4 = 12

Attack
//eighth turn, Ricky does attack
//(8*,4*) -> damage = 8+4 = 12

TheEnd
//end tag. if you reach this tag it means the input is over.

• Now you need to tell your uncle:

  1. how Ricky summon the monsters:

     //Ricky's summon structure will be like:
            real world
          /           \
         8*           4*
       /   \
      4*    5*
             \
             3*
     // Ricky needs to follow the preorder traversing:
     ->8* 4* 5* 3* 4* 
     (don't show root node("real world") in your answer!!)
     

     So the answer will be: 8* 4* 5* 3* 4*

  2. Sum of all star points Ricky gave to the wall:
     9+12+12=33
     So the answer will be 33.

  3. the output format should be like: 8* 4* 5* 3* 4*\n33\n
  4. \n is newline

 

Input

input template:

Summon -> 4* 
Summon -> 3* 
Summon -> 5* 
Attack
Summon -> 8*
Summon -> 4*
Attack
Attack
TheEnd

 

Output

Output template:

8* 4* 5* 3* 4*
33

Sample Input  Download

Sample Output  Download

Tags

Discuss