Under construction

Still being built. Things may change

Kitten of Chaos

Interview

Time limit1sMemory limit1024 MB

Summary
Given a string of b, d, p, q and a sequence of h, v, r flips and rotations, find the string seen after all transformations are applied in order.
Level

Medium4 of 10

Topics
String, Bit manipulation, Simulation
Solved
No attempts yet

Problem

Karen keeps a beautiful, precious glass object on the shelf in her living room. Unfortunately, her cat Klaus does not like having things on his favorite shelf. Anything that is not bolted or glued in place, he gradually pushes over the edge while looking Karen straight in the eyes.

Now Klaus's paw slowly carries out his diabolical deed. His cute, fluffy face radiates unintentional innocence. Knowing that any intervention would only delay the inevitable, Karen wonders what will happen to the string her sister Kim wrote on the glass object. It took Kim a whole week to gather all the bdpq letters that make up the string.

Can you describe what the string will look like from Karen's point of view while the object tumbles toward destruction?

While the object falls, it is subject to the following transformations, described as seen when looking at the object from the front.

  • h: horizontal flip, e.g. bbq becomes pdd
  • v: vertical flip, e.g. bbq becomes ppd
  • r: 180-degree rotation, e.g. bbq becomes bqq

No flips along or rotations about any other axes are possible.

Input

One line with a string ss consisting of the letters bdpq (1≤∣s∣≤5⋅1051 \le |s| \le 5\cdot 10^5), the string printed on the glass object as seen at the start of the fall.

One line with a string tt consisting of the letters hvr (1≤∣t∣≤5⋅1051 \le |t| \le 5\cdot 10^5), the sequence of transformations in the order they occur during the fall.

Output

Output the string that can be seen at the moment the glass object touches the ground, just before it shatters into pieces.

Examples4

  1. Example 1

    Input
    bbq
    h
    
    Expected output
    pdd
    
  2. Example 2

    Input
    bbq
    v
    
    Expected output
    ppd
    
  3. Example 3

    Input
    bbq
    r
    
    Expected output
    bqq
    
  4. Example 4

    Input
    ppbddbq
    hvrhv
    
    Expected output
    bqppqdd