跳至正文
题库2945
#2945

Parity Game

查看题目操作

Parity Game

题目描述

You are fishing with polar bears Alice and Bob. While waiting for the fish to bite, the polar bears get bored. They come up with a game. First Alice and Bob each writes a 01-string (strings that only contain character "0" and "1") a and b. Then you try to turn a into b using two types of operations:

  • Write parity(a) to the end of a. For example, .
  • Remove the first character of a. For example, . You cannot perform this operation if a is empty.

You can use as many operations as you want. The problem is, is it possible to turn a into b?

The parity of a 01-string is 1 if there is an odd number of "1"s in the string, and 0 otherwise.

Input

The first line contains the string a and the second line contains the string b (1≤|a|,|b|≤1000). Both strings contain only the characters "0" and "1". Here |x| denotes the length of the string x.

Output

Print "YES" (without quotes) if it is possible to turn a into b, and "NO" (without quotes) otherwise.

Examples

01011
0110
YES
0011
1110
NO

Note

In the first sample, the steps are as follows: 01011→1011→011→0110