The Little Girl loves problems on games very much. Here's one of them.

Two players have got a string *s*, consisting of lowercase English letters. They play a game that is described by the following rules:
 -  The players move in turns; In one move the player can remove an arbitrary letter from string *s*. -  If the player before his turn can reorder the letters in string *s* so as to get a palindrome, this player wins. A palindrome is a string that reads the same both ways (from left to right, and vice versa). For example, string "abba" is a palindrome and string "abc" isn't. 
Determine which player will win, provided that both sides play optimally well — the one who moves first or the one who moves second.
The input contains a single line, containing string *s* (1 ≤ |*s*|  ≤  10<sup class="upper-index">3</sup>). String *s* consists of lowercase English letters.
import sys
from collections import defaultdict


def main() -> None:
    read = sys.stdin.readline
    word = [c for c in read().strip()]
    read()
    swaps = [int(i) for i in read().split()]
    frequency_swaps = [0] * (len(word) + 1)

    for swap in swaps:
        frequency_swaps[swap] += 1
    for i in range(1, len(frequency_swaps)):
        frequency_swaps[i] += frequency_swaps[i - 1]

    for i in range(len(word) // 2):
        # Num of swaps at this point
        swap_count = frequency_swaps [i + 1]
        if swap_count % 2 != 0:
            word[i], word[-i + -1] = word[-i + -1], word[i]

    print(''.join(word))


if __name__ == '__main__':
    main()