背景

本题和 Easy ver. 只有数据范围的区别。

本题的常规版在入门题库。

题目描述

Alice 快要过生日了，她邀请了很多位好朋友参加她的生日宴会。所有朋友的名字长度均仅由大小写字母构成。

然而她的朋友们都很忙，不确定能否参加，无法给她一个明确的答复。她收到的回复可分为下面三类（其中 $A,B$ 为任意人名）：

• A=>B：如果 $A$ 参加，那么 $B$ 也参加。
• A<=B：如果 $B$ 参加，那么 $A$ 也参加。
• A<=>B：如果 $A$ 参加，那么 $B$ 也参加，反之亦然。

她可以把这些回复串起来，例如她用 Andrea=>Bob<=Cindy 来表示：

• 如果 Andrea 参加，那么 Bob 一定参加。
• 如果 Cindy 参加，那么 Bob 也一定参加。

她发现所有朋友的回复可以构成一个字符串 $s$，并且 $s$ 没有重复人名。

Alice 把这个字符串告诉了你，接着她会问你 $q$ 个问题，每次给你两个人 $u,v$，她想知道，如果 $u$ 参加生日宴会，那么 $v$ 是否一定会参加。

输入格式

输入的第一行有一个字符串 $s$，表示所有朋友的回复形成的字符串。

第二行有一个正整数 $q$，表示问题的个数。

之后 $q$ 行，每行有两个人名 $u,v$，表示一个问题。

输出格式

对于每个问题，输出一行一个字符串：“如果 $u$ 参加，那么 $v$ 一定参加”若成立，输出 Yes，否则输出 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

提示

【样例 1 解释】

对于每个询问我们依次解释：

• 根据 Andrea=>Bob，如果 Andrea 参加，那么 Bob 参加。
• 根据 Cindy<=>Dora，如果 Dora 参加，那么 Cindy 参加。
• 如果 Dora 参加，那么 Cindy 会参加，而这也就意味着 Bob 会参加，因此，如果 Dora 参加，那么 Bob 参加。
• 对于第 $4$ 组询问，可以构造“仅 Andrea, Bob 参加”的反例，因此，如果 Andrea 参加，则 Cindy 不一定参加。
• 对于第 $5,6$ 组询问，由于我们不知道关于 Mike 的任何回复，显然答案是不一定。
• 但是第 $7$ 组询问不一样——“如果 Mike 参加，那么 Mike 一定参加了”是一句废话，这是永远成立的。

【数据范围】

对于全部数据，保证：

• $s$ 由不重复人名组成，人名之间的间隔必为 <=，=> 和 <=> 之一。
• 每个人名仅由英文字母组成，首字母大写，其他字母小写，并且这些人名都不是 Alice。
• $|s|\le 3\times 10^6$，所有询问中出现的人名长度和 $\le 3\times 10^6$。