题目描述

Okarun 一直痴迷于外星人存在的想法。他小时候尝试过各种联系外星人的方式，但都没有成功。这并不奇怪，因为外星人说的是一种完全不同的语言！

有一天，他读到一篇文章，说外星人实际上也使用小写拉丁字母书写，但读词的方式完全不同。

在外星语言中，有 $n+26$ 种不同的声音，每种声音由一个拉丁字母串 $s_i$ 表示。已知对于 $1\le i\le 26$，第 $i$ 种声音由长度为 $1$ 的字符串表示，即第 $i$ 个小写拉丁字母。对于 $i>26$，第 $i$ 种声音由长度至少为 $2$ 的小写拉丁字母串表示。

当外星人读一个单词 $x$ 时，他从第一个位置开始。若当前位于位置 $i$，他会寻找一个声音 $s_j$，使得 $s_j$ 从位置 $i$ 开始作为 $x$ 的子串出现。如果有多个这样的声音，他选择长度最大的那个声音 $s_j$。然后他读出该声音，并移动到位置 $i+|s_j|$，继续读，直到整个单词读完。注意，由于每个小写拉丁字母本身都是一种声音，因此任何单词都总能被读出。

后来还发现，有些外星声音虽然写法不同，但实际发音相同。也就是说，存在一些声音字符串 $s_i$ 和 $s_j$（$i\ne j$，$s_i\ne s_j$），它们表示相同的声音。并且这种相同关系具有传递性：如果 $s_i$ 与 $s_j$ 被认为相同，$s_j$ 与 $s_l$ 被认为相同，那么 $s_i$ 与 $s_l$ 也被认为相同。

外星人称某些单词为同音词：它们听起来相同，拼写可以相同也可以不同。换句话说，若两个单词 $v,w$ 按外星语言读出后得到的声音序列完全相同，则它们是同音词。

Okarun 写了一段由小写拉丁字母组成的文本 $t$。他想研究 $q$ 对文本子串。每对中，第一个子串是文本中从第 $a_i$ 个字符到第 $b_i$ 个字符（含两端），第二个子串是从第 $c_i$ 个字符到第 $d_i$ 个字符（含两端）。对于每一对子串，Okarun 想知道它们在外星语言中是否是同音词。

子串的定义：一个字符串的子串可以通过从原字符串开头删除若干字符，并从结尾删除若干字符得到，删除数量可以为零。

输入格式

第一行包含一个非空字符串 $t$（$1\le |t|\le 500000$），由小写拉丁字母组成。

第二行包含两个整数 $n,k$（$0\le n\le 500000$，$0\le k<n+26$），分别表示长度至少为 $2$ 的声音数量，以及 Okarun 记录的相同声音对数量。

接下来 $n$ 行描述从第 $27$ 种声音开始的声音。第 $i$ 行包含一个非空字符串 $s_{i+26}$（$2\le |s_{i+26}|\le 10^6$），由小写拉丁字母组成，表示第 $i+26$ 种声音。保证所有声音字符串两两不同。注意，输入中不会出现 a 到 z 这些单字母声音，但每个测试中它们都默认作为编号 $1$ 到 $26$ 的声音存在。

接下来 $k$ 行描述 Okarun 最初记录的相同声音对。每行包含两个整数 $x_i,y_i$（$1\le x_i,y_i\le n+26$，$x_i\ne y_i$），表示 Okarun 认为编号为 $x_i$ 与 $y_i$ 的两个声音发音相同。保证每对编号最多出现一次。注意，其他声音对的相同关系可能由传递性推出。

下一行包含一个整数 $q$（$1\le q\le 300000$），表示需要判断的子串对数量。

接下来 $q$ 行，每行包含四个整数 $a_i,b_i,c_i,d_i$（$1\le a_i\le b_i\le |t|$，$1\le c_i\le d_i\le |t|$），表示两个子串：第一个为文本 $t$ 中位置 $a_i$ 到 $b_i$，第二个为位置 $c_i$ 到 $d_i$。

设 $S$ 为所有额外声音字符串长度之和，即不包含 a 到 z 的声音时，

保证 $S\le 10^6$。

输出格式

输出 $q$ 行。对于第 $i$ 个询问，如果两个子串在外星语言中同音，输出 Yes；否则输出 No。

样例

abracadabra
2 3
cada
ca
1 27
1 28
1 4
4
5 11 1 4
4 6 5 7
5 7 5 8
2 5 2 5

Yes
Yes
No
Yes

样例解释

第一个询问中：

• 第一个子串 cadabra 会被读作声音：cada, b, r, a；
• 第二个子串 abra 会被读作声音：a, b, r, a。

声音 cada 与 a 被记录为相同（编号对 $(1,27)$），因此这两个子串是外星同音词。

第二个询问中：

• 第一个子串 aca 会被读作声音：a, ca；
• 第二个子串 cad 会被读作声音：ca, d。

声音 a 与 ca 被记录为相同（编号对 $(1,28)$），声音 ca 与 d 也相同（因为编号 $(1,4)$ 与 $(1,28)$ 的声音相同，所以编号 $4$ 与 $28$ 也相同）。因此这两个子串也是外星同音词。

第三个询问中：

• 第一个子串 cad 会被读作声音：ca, d；
• 第二个子串 cada 会被读作声音：cada。

声音数量不同，因此它们一定不是外星同音词。

第四个询问给出了两个相同子串，因此读法相同，是外星同音词。

评分方式

本题测试点由 10 个分组组成。只有通过某一组及其要求的部分前置分组时，才能获得该组分数。注意，部分分组不要求通过样例。Offline-testing 表示该组测试结果只会在比赛结束后给出。

| 组别 | 分数 | 附加限制：$|t|$ | 附加限制：$S$ | 附加限制：$q$ | 依赖分组 | 说明 | | ---- | ---: | --------------: | ------------: | ------------: | -------- | --------------- | | 0 | 0 | - | - | - | - | 样例 | | 1 | 8 | $|t|\le 500$ | $S\le 500$ | $q\le 500$ | 0 | - | | 2 | 7 | $|t|\le 6000$ | $S\le 6000$ | $q\le 6000$ | - | $b_i=d_i=|t|$ | | 3 | 9 | $|t|\le 6000$ | $S\le 6000$ | $q\le 200000$ | 2 | $b_i=d_i=|t|$ | | 4 | 15 | $|t|\le 200000$ | $S\le 200000$ | $q\le 200000$ | 2,3 | $b_i=d_i=|t|$ | | 5 | 8 | $|t|\le 6000$ | $S\le 6000$ | $q\le 200000$ | - | $a_i=c_i=1$ | | 6 | 6 | $|t|\le 500$ | $S\le 500$ | $q\le 200000$ | 0,1 | - | | 7 | 7 | $|t|\le 6000$ | $S\le 6000$ | $q\le 6000$ | 0–2 | - | | 8 | 10 | $|t|\le 6000$ | $S\le 200000$ | $q\le 6000$ | 0–2,7 | - | | 9 | 19 | $|t|\le 200000$ | $S\le 400000$ | $q\le 200000$ | 0–8 | - | | 10 | 11 | - | - | - | 0–9 | Offline-testing |