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.


-----Input-----

The input contains a single line, containing string s (1 ≤ |s|  ≤  10^3). String s consists of lowercase English letters.


-----Output-----

In a single line print word "First" if the first player wins (provided that both players play optimally well). Otherwise, print word "Second". Print the words without the quotes.


-----Examples-----
Input
aba

Output
First

Input
abca

Output
Second

Difficulty: interview

Starter code:

Solutions:
def __starting_point():
    s = input()
    c = [s.count(x) for x in set(s)]
    total = 0
    for x in c:
        if x % 2 != 0:
            total += 1
    if total % 2 == 0 and total != 0:
        print("Second")
    else:
        print("First")

__starting_point()

from collections import *
x=sum(i%2for i in list(Counter(input()).values()))
print("SFeicrosntd"[x%2+(x<1)::2])


s=input();x=sum(s.count(i)%2for i in s)
print("SFeicrosntd"[x%2+(x<1)::2])


import sys
s=sys.stdin.readline().strip()
hash=[0]*256
for ch in s:
    hash[ord(ch)-97]+=1
count=0
for i in range(256):
    count+= (1 if hash[i]%2!=0 else 0)
if count==0 or count%2!=0:
    print("First")
else:
    print("Second")

def main():
          s=input()
          n=list(s)
          n.sort()
          k=0
          f=0
          i=0
          while(i<len(s)):
                  if(n.count(n[i])==1 and f==0 ):
                                                   f=1
                                                   
                  else:    
                       if(n.count(n[i])%2!=0):
                                              k=k+n.count(n[i])
                                              
                  i=i+n.count(n[i])
                    
          if(k==0):
              print("First")
              return
          if(f==0):
               if(k%2!=0):
                     print("First")
                     return
               else:
                     print("Second")
                     return
          else:
             if(k%2==0):
                  print("First")
                  return
             else:
                 print("Second")
                 return
main()

s=input()
n=len(s)
def if_palindrome(s):
    x=list(s)
    y=list(s)
    y.reverse()
    if(x==y):
        return True
    return False



done=False
x=list(s)
x=list(set(x))
nn=len(x)
r=0
for i in range(nn):
    if(s.count(x[i])%2==1):
        r+=1
    if(r>1):
        break
if(r<=1):
    print("First")
    done=True


    

if(not done):
    n=len(s)
    if(n%2==1):
        print("First")
    else:
        print("Second")
    


import collections

def palindromic(f, l):
    if l % 2 == 0:
        return len(odds(f)) == 0
    else:
        return len(odds(f)) == 1

def odds(f):
    return [k for (k,v) in list(f.items()) if v % 2 == 1]
def evens(f):
    return [k for (k,v) in list(f.items()) if v % 2 == 0 and v > 0]

s = input()
f = collections.defaultdict(int)
l = len(s)

# count character frequencies in s
for c in s:
    f[c] += 1

while not palindromic(f, l):
    o = odds(f)

    # if there are too many odds, remove one
    if len(o) >= 1:
        f[o[0]] -= 1
    else:
        f[evens(f)[0]] -= 1

    l -= 1

print("First" if (len(s) - l) % 2 == 0 else "Second")


3

s = sorted(list(input()))
tmp = [len([1 for i in s if c == i]) % 2 for c in set(s)]
if sum(tmp) == 0 or sum(tmp) % 2 == 1:
    print('First')
else:
    print('Second')


# import sys
# f = sys.stdin
# f = open("input.txt", "r")
a = input()
b = dict()
for i in set(a):
    if a.count(i)%2 != 0:
        b[i] = a.count(i)
if len(b) > 1:
    if (len(b)-1)%2:
        print("Second")
    else:
        print("First")
else:
    print("First")

import sys

mem = {}

def palindrome_set_counts(string):
    if string == "":
        return True
    
    counts = {}
    for letter in string:
        if letter not in counts:
            counts[letter] = 0
        counts[letter] += 1
        counts[letter] %= 2

    letter_sums = 0
    for key, value in list(counts.items()):
        letter_sums += value

    return letter_sums

def who_wins():
    results = [1, 1, -1, 1]
    for i in range(4, 2000000):
        results.append(results[i-1] * -1)

    return results

counts = palindrome_set_counts(sys.stdin.readline().strip())
print("First" if who_wins()[counts] == 1 else "Second")
        


from string import ascii_lowercase
s = input()

k = 0
for c in ascii_lowercase:
    if s.count(c) % 2 != 0:
        k += 1

if k == 0 or k == 1 or k % 2 != 0:
    print("First")
else:
    print("Second")


t, p = input(), {}
for i in t:
    p[i] = p.get(i, 0) + 1
s = sum(p[i] % 2 for i in p)
if s < 2: print('First')
elif s % 2 == 0: print('Second')
else: print('First')


import sys

MIN = -1000000000
MAX = -MIN

def odds_evens(string):
    f = {}
    for letter in string:
        if letter not in f:
            f[letter] = 0
        f[letter] += 1

    n_odds, n_evens = 0, 0
    for key, val in list(f.items()):
        if val % 2 != 0:
            n_odds += 1
        else:
            n_evens += 1

    return (n_odds, n_evens)

string = sys.stdin.readline().strip()
n_odds, n_evens = odds_evens(string)

if n_odds == 0:
    print("First")
elif n_odds % 2 == 0:
    print("Second")
else:
    print("First")
    


s=input()
n=len(s)
if(n%2==1):
    print('First')
else:
    l=[0]*26
    for i in s:
        if(i=='a'): l[0]+=1
        elif(i=='b'): l[1]+=1
        elif(i=='c'): l[2]+=1
        elif(i=='d'): l[3]+=1
        elif(i=='e'): l[4]+=1
        elif(i=='f'): l[5]+=1
        elif(i=='g'): l[6]+=1
        elif(i=='h'): l[7]+=1
        elif(i=='i'): l[8]+=1
        elif(i=='j'): l[9]+=1
        elif(i=='k'): l[10]+=1
        elif(i=='l'): l[11]+=1
        elif(i=='m'): l[12]+=1
        elif(i=='n'): l[13]+=1
        elif(i=='o'): l[14]+=1
        elif(i=='p'): l[15]+=1
        elif(i=='q'): l[16]+=1
        elif(i=='r'): l[17]+=1
        elif(i=='s'): l[18]+=1
        elif(i=='t'): l[19]+=1
        elif(i=='u'): l[20]+=1
        elif(i=='v'): l[21]+=1
        elif(i=='w'): l[22]+=1
        elif(i=='x'): l[23]+=1
        elif(i=='y'): l[24]+=1
        else: l[25]+=1
    c=0
    for i in l:
        if(i%2==1):
            c+=1
    if(c==0):
        print('First')
    else:
        print('Second')


s = input()
a = [0]*26
for c in s:
    a[ord(c)-ord('a')] += 1

cnt = 0
for i in range(26):
    if a[i] % 2 == 1: cnt += 1
    
if cnt == 0:
    print('First')
elif cnt % 2 == 0:
    print('Second')
else:
    print('First')



def main():
    s = input()
    
    liters = [0 for i in range(26)]
    for i in s:
        liters[ord(i) - ord('a')] ^= 1
    
    c = liters.count(1)
    
    if c == 0 or c % 2 == 1:        #c % 2 or n % 2
        print("First")
    else:
        print("Second")

main()


s = input();
cnt = sum(s.count(i) % 2 for i in s)
if (cnt % 2 == 1 or cnt == 0):
	print("First");
else:
	print("Second");

x=input()
ch = nch = 0
for i in 'abcdefghijklmnopqrstuvwxyz':
    if x.count(i)>0:
        if x.count(i)%2==0:
            ch+=1
        else:
            nch+=1

t = 0
while nch > 1:
    if ch > 0:
        ch-=1
        nch+=1
    else:
        nch-=1
    t = (t+1)%2
print('First' if t==0 else 'Second')


x=input()
ch = nch = 0
for i in 'abcdefghijklmnopqrstuvwxyz':
    if x.count(i)>0:
        if x.count(i)%2==1:
            nch+=1

t = 0
nch+=ch
while nch > 1:
    nch-=1
    t = (t+1)%2
print('First' if t==0 else 'Second')


from collections import Counter
cnt = Counter(input())
s = sum([a[1] % 2 for a in list(cnt.items())])
print('First' if s <= 1 or s % 2 else 'Second')


def main():
    l = [0] * 26
    for c in input():
        l[ord(c) - 97] ^= 1
    x = l.count(1)
    print(('Second', 'First')[not x or x & 1])


def __starting_point():
    main()
__starting_point()

l=input()

abc="abcdefghijklmnopqrstuvwxyz"

x=sum(l.count(i)%2 for i in abc)

if (x==0 or x%2==1):print("First")
else:print("Second")

m = list(input())

d = {}

for c in m:
    if c in d:
        d[c] += 1
    else:
        d[c] = 1

cnt = 0

for c in d:
    if d[c] % 2:
        cnt += 1

if not cnt:
    print('First')
else:
    if cnt % 2:
        print('First')
    else:
        print('Second')

# coding: utf-8
s = input()
cnt = [0,0]
for i in set(s):
    cnt[s.count(i)%2] += 1
if (cnt[1] and cnt[1]%2) or (not cnt[1]):
    print('First')
else:
    print('Second')


s = input()
c = 0
a = []
i = 0
b = 0

while c<len(s):
    if s[i] not in a:
        x = s.count(s[i])
        if x%2 == 1:
            b += 1
        c += x
        a.append(s[i])
    
    i += 1

if b==0 or b%2 == 1:
    print ("First")
else:
    print ("Second")