Background

This problem differs from the Easy ver. only in the constraints.

The regular version of this problem is in the beginner problem set.

Problem Description

Alice’s birthday is coming soon, and she invited many good friends to her birthday party. All friends’ names consist only of uppercase and lowercase letters.

However, her friends are all busy and are not sure whether they can attend, so they cannot give her a clear answer. The replies she receives can be divided into the following three types (where $A, B$ are any names):

• A=>B: If $A$ attends, then $B$ also attends.
• A<=B: If $B$ attends, then $A$ also attends.
• A<=>B: If $A$ attends, then $B$ also attends, and vice versa.

She can concatenate these replies. For example, she uses Andrea=>Bob<=Cindy to mean:

• If Andrea attends, then Bob will definitely attend.
• If Cindy attends, then Bob will definitely attend as well.

She found that all her friends’ replies can form a string $s$, and $s$ contains no repeated names.

Alice tells you this string, and then she will ask you $q$ questions. Each time she gives you two names $u, v$, and she wants to know whether, if $u$ attends the birthday party, then $v$ must attend.

Input Format

The first line contains a string $s$, representing the string formed by all friends’ replies.

The second line contains a positive integer $q$, representing the number of queries.

The next $q$ lines each contain two names $u, v$, representing one query.

Output Format

For each query, output one line with a string: if “if $u$ attends, then $v$ must attend” is true, output Yes; otherwise output No.

Andrea=>Bob<=Cindy<=>Dora
7
Andrea Bob
Dora Cindy
Dora Bob
Andrea Cindy
Andrea Mike
Mike Andrea
Mike Mike

Yes
Yes
Yes
No
No
No
Yes

Hint

[Sample 1 Explanation]

We explain each query in order:

• From Andrea=>Bob, if Andrea attends, then Bob attends.
• From Cindy<=>Dora, if Dora attends, then Cindy attends.
• If Dora attends, then Cindy will attend, which also means Bob will attend. Therefore, if Dora attends, then Bob attends.
• For the $4$-th query, we can construct a counterexample where “only Andrea and Bob attend”. Therefore, if Andrea attends, Cindy does not necessarily attend.
• For the $5$-th and $6$-th queries, since we do not know any reply about Mike, the answer is clearly not guaranteed.
• But the $7$-th query is different: “if Mike attends, then Mike must attend” is a meaningless statement, and it is always true.

[Constraints]

For all testdata, it is guaranteed that:

• $s$ consists of non-repeated names, and the separator between names must be one of <=, =>, and <=>.
• Each name consists only of English letters, with the first letter uppercase and the other letters lowercase, and none of these names is Alice.
• $|s|\le 3\times 10^6$, and the sum of name lengths appearing in all queries is $\le 3\times 10^6$.

Translated by ChatGPT 5