Two people are playing a game with a string $s$, consisting of lowercase latin letters. 

On a player's turn, he should choose two consecutive equal letters in the string and delete them. 

For example, if the string is equal to "xaax" than there is only one possible turn: delete "aa", so the string will become "xx". A player not able to make a turn loses.

Your task is to determine which player will win if both play optimally.


-----Input-----

The only line contains the string $s$, consisting of lowercase latin letters ($1 \leq |s| \leq 100\,000$), where $|s|$ means the length of a string $s$.


-----Output-----

If the first player wins, print "Yes". If the second player wins, print "No".


-----Examples-----
Input
abacaba

Output
No

Input
iiq

Output
Yes

Input
abba

Output
No



-----Note-----

In the first example the first player is unable to make a turn, so he loses.

In the second example first player turns the string into "q", then second player is unable to move, so he loses.

Difficulty: interview

Starter code:

Solutions:
s = input()

l = []
t = 0

for i in range(len(s)):
    if len(l) > 0:
        if s[i] == l[-1]:
            l.pop()
            t += 1
        else:
            l.append(s[i])
    else:
        l.append(s[i])

if t % 2 == 0:
    print("No")
else:
    print("Yes")


res = 1
stack = ['1', '2']
for c in input():
    sp = stack.pop()
    if c != sp:
        stack.append(sp)
        stack.append(c)
    else:
        res = 3 - res
if res != 1:
    print('Yes')
else:
    print('No')


s=list(input())
a=['*']
d=0
for i in range(len(s)):
    if s[i]==a[-1]:
        a.pop()
        d+=1
    else:
        a.append(s[i])
if d%2==1:
    print("Yes")
else:
    print("No")                 

n = input()
s = ""
m = 0
s += n[0]
for i in range(len(n)-1):
    if(len(s) > 0):
        if(n[i+1] == s[-1]):
            s=s[:len(s)-1]
            m+=1
        else:
            s+=n[i+1]
    else:
        s+=n[i+1]
if(m%2==1):
    print("Yes")
else:
    print("No")


import sys
input = sys.stdin.readline
from  collections import deque


d = deque()
s = input()
c = 0

for l in s:
    d.append(l)
    if len(d) >= 2 and d[-1] == d[-2]:
        d.pop()
        d.pop()
        c += 1

print("Yes" if c%2 else "No")

st=[]
s=input()
cn=0

for i in s:
    st.append(i)
    while len(st)>=2 and st[-2]==st[-1]:
        st.pop()
        st.pop()
        cn+=1

print("Yes" if cn%2==1 else "No")

#!/usr/bin/env python
# coding: utf-8

# In[19]:


word=list(input())


# In[20]:


n=len(word)


# In[21]:


emptyword=[]


# In[22]:


popcount=0


# In[23]:


for i in range(n):
    if len(emptyword)==0:
        emptyword=[word[i]]
    else:
        if word[i]==emptyword[-1]:
            emptyword.pop()
            popcount+=1
        else:
            emptyword.append(word[i])
                     


# In[24]:


if popcount%2==0:
    print('No')
else:
    print('Yes')


# In[ ]:






s = input()

n = 0
l = [0]
for c in s:
    if l[-1] == c:
        n += 1
        l.pop()
    else:
        l.append(c)

if n % 2 == 0:
    print( "No" )
else:
    print("Yes")


from collections import deque
S=input()
H=deque()
N=len(S)
num=0
for i in range(N):
    if len(H)>0 and H[-1]==S[i]:
        num+=1
        H.pop()
    else:
        H.append(S[i])
    #print(H)
#print(num)
if num%2==1:
    print('Yes')
else:
    print('No')


i=input()
l=[]
p=''
o=0
nuz=0
while o<len(i):
    p=i[o]
    if p >= 'a' and p <= 'z':
        if len(l)==0 or l[len(l)-1]!=p:
            l.append(p)
        else:
             l.pop()
             nuz+=1
    o+=1
if nuz%2==0:
    print('No')
else:
    print('Yes')


s = input()

left = ['*']
cnt = 0
for ch in s:
    if ch == left[-1]:
        left.pop()
        cnt += 1
    else:
        left.append(ch)

print(['No', 'Yes'][cnt%2])


s=input()
x=[]
ans=0
for i in s:
  x.append(i)
  if len(x)>=2 and x[-1]==x[-2]:
    ans+=1
    x.pop()
    x.pop()
if ans%2==0:
  print("No")
else:
  print("Yes")

s = input()
lis = []
cnt = 0
for c in s:
    lis.append(c)
    if len(lis)>1:
        if lis[-1]==lis[-2]:
            lis.pop()
            lis.pop()
            cnt = cnt+1
if cnt%2==0:
    print('No')
else:
    print('Yes')


s = input()

w = 1

l = []

for c in s:
	if(len(l)==0):
		l.append(c)
	elif(l[-1]==c):
		w = (w+1)%2
		l.pop()
	else:
		l.append(c)

if(w==0):
	print("Yes")
else:
	print("No")

S=list(input())

from collections import deque
QUE=deque()
QUE.append("START")
QUE.append("!")
ANS=0

for s in S:
    QUE.append(s)

    while QUE[-1]==QUE[-2]:
        QUE.pop()
        QUE.pop()
        ANS+=1

if ANS%2==0:
    print("No")
else:
    print("Yes")
    


s = input()
st = ['']
k = 0
for c in s:
	if c == st[-1]:
		k += 1
		st.pop()
	else:
		st.append(c)

print('Yes' if k % 2 == 1 else "No")


# -*- coding: utf-8 -*-
# @Time    : 2019/1/22 22:47
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : B. Game with string.py


def main():
    s = input()
    times, stack = 0, []
    for c in s:
        if not stack or stack[-1] != c:
            stack.append(c)
        else:
            stack.pop()
            times += 1
    print('Yes' if times % 2 else 'No')


def __starting_point():
    main()

__starting_point()

s = input()
n = len(s)
stack = []
c = 0
for i in range(n):
    if stack and stack[-1] == s[i]:
        stack.pop()
        c += 1
    else:
        stack.append(s[i])
if c % 2 == 1:
    print('Yes')
else:
    print('No')


s = '^'+input()+'$'
n = len(s)
N = [*list(range(1,n+1))]
P = [*list(range(-1,n-1))]

count = 0

i = 0
while N[i] != n:
    if s[i] == s[N[i]]:
        P[N[N[i]]] = P[i]
        N[P[i]] = N[N[i]]
        i = P[i]
        count += 1
    else:
        i = N[i]

print('Yes' if count%2 else 'No')

#print(count)
#i = 0
#while i != n:
#    print(s[i], end='')
#    i = N[i]
#print()


from collections import deque

s = input()
counter = 0
q = deque()
q.append("123123123123123")
for i in s:
    last = q.pop()
    if i != last:
        q.append(last)
        q.append(i)
    else:
        if last == i:
            counter += 1
print("Yes" if counter%2==1 else "No")


s = input()
w = 1
l = []
for c in s:
    if(len(l)==0):
        l.append(c)
    elif(l[-1] == c):
        l.pop()
        if(w==1):
            w = 2
        else:
            w = 1

    else:
        l.append(c)
if(w==1):
    print("No")
else:
    print("Yes")



s=list(input())
st=[]
cnt=0
for i in s:
    if len(st)==0 or st[-1]!=i:
        st.append(i)
    elif st[-1]==i:
        st.pop()
        cnt+=1
if cnt&1:print('Yes')
else:print('No')

s=list(input())
d=[s[0]]
count=0
for i in range(1,len(s)):
    if len(d)==0:
        d.append(s[i])
    else:
        x=d.pop()
        if x==s[i]:
            count+=1
        else:
            d.append(x)
            d.append(s[i])
if count%2==0:
    print("No")
else:
    print("Yes")