Card Shuffling

Interview

Time limit2sMemory limit1024 MB

Summary

Given a deck string read from the bottom and a repeat count k, simulate the shuffle where cards alternate into left and right piles and the left pile is placed on top, k times.

Level: Medium4 of 10
Topics: Implementation, Simulation, Array, String
Solved: No attempts yet

Problem

Petya and Vasya play a fun game with cards. The game is very simple. There is a deck of cards, each with a Latin letter written on it. The cards are shuffled, dealt to the players, and they form words from them.

Vasya wants to cheat a little. He knows the order in which the cards lie in the deck and how Petya shuffles them. From this data he wants to find out how the cards will lie after the shuffle.

The cards are shuffled in several stages. At each stage Petya first takes the cards from the deck one by one from top to bottom and lays them into two piles: one to the left, one to the right, one to the left, one to the right. After that he puts the left pile on top of the right pile. These actions are repeated $k$ times.

Help Vasya determine how the cards will lie in the deck after the shuffle.

Input

The first line of the input contains a string describing the state of the deck before shuffling. The string consists of uppercase Latin letters. The $i$ -th letter of the string corresponds to the $i$ -th card from the bottom of the deck. The length of the string does not exceed 100 characters.

The second line contains an integer $k$ ( $1\le k\le 100$ ).

Output

Output the state of the deck after shuffling in the same format as in the input.

Examples1

Example 1
Input
```
ABCDEFG
1
```
Expected output
```
FDBGECA
```