Problem Description

Currently, there are $ M $ enemies, and the $ i $th enemy is initially $ x_i + 0.5 $ units away from where you are, moving closer by 1 unit per second. When an enemy reaches a distance of $ 0 $ from you, you die. Specifically, you die when an enemy at a distance of $ 0.5 $ moves even closer.
Each enemy has a unique string consisting of 0 and 1, and the string for the $ i $th enemy is $ s_i $.

You have a weapon that also has a string $ S $ consisting of 0 and 1. You can perform the following two actions with your weapon:

• Defeat the nearest enemy, but only if your weapon's string is lexicographically larger than the enemy's string.
• Cast a spell on your weapon over 1 second to change its string.

The time taken for an attack is negligible, and you do not move from your initial position during either action.

The spell you can use changes your weapon's string as follows:

• Add two 0s to the beginning of the string.
• For each character, write a 0 if the adjacent characters to the right and left are the same, or a 1 if they are different. If either the right or left character does not exist, write nothing.
• The string written below becomes the new string.

For example, if your weapon has the string 1101, after casting the spell, the new string will be 1110 as follows:

Given the information about $ M $ enemies and the initial string $ S $ of your weapon, determine if you can survive without being killed by any enemy.

Input Format

The input is given from the standard input in the following format:

$ S $ $ M $ $ x_1 $ $ s_1 $ $ x_2 $ $ s_2 $ : $ x_M $ $ s_M $

Output Format

Output Yes if you can defeat all enemies before their distance reaches $ 0 $, otherwise output No.

Sample Input and Output

Sample Input #1

1101
2
1 1001
2 1101

Sample Output #1

Yes

Sample Input #2

1101
2
1 1001
2 1110

Sample Output #2

No

Sample Input #3

1111
4
1 1
2 011
3 1100
7 0000001

Sample Output #3

Yes

Sample Input #4

00000000
1
1000000000000000000 1

Sample Output #4

No

Sample Input #5

0110011000
10
1 100
2 0111
3 0000
5 1
5 0
6 0000001
7 11
7 00
8 00
9 0101

Sample Output #5

No

Notes/Hints

Constraints

• $0 \leq M \leq 10^5$
• $0 < x_1 \leq x_2 \leq \dots \leq x_M \leq 10^{18}$
• $1 \leq |s_i| \ (i=1,2,\dots,M)$
• $\displaystyle\sum_{i=1}^M |s_i| \leq 10^5$
• $1 \leq |S| \leq 10^5$
• $ s_i $ and $ S $ are strings consisting only of 0 or 1

见题面 Input 部分

见题面 Output 部分