Game with string

1000ms

262144K

Description:

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".

Sample Input:

abacaba

Sample Output:

No

Sample Input:

iiq

Sample Output:

Yes

Sample Input:

abba

Sample 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.

Informação

Provedor Codeforces

Código CF1104B