【题目背景】

Yazid 和 Tiffany 喜欢字符串问题。在这里，我们将给你介绍一些关于字符串的基本概念。

对于一个字符串 S，我们定义 |S | 表示 S 的长度。

接着，我们定义该串的子串 S (L, R) 表示由 S 中从左往右数，第 L 个字符到第 R个字符依次连接形成的字符串，特别地，如果 L < 1 或 R > |S | 或 L > R，则 S (L, R) 表 示空串。

我们说两个字符串相等，当且仅当它们的长度相等，且从左至右各位上的字符依次相同。

我们说一个字符串 T 是 S 的前. 缀. ，当且仅当 S (1, |T|) = T。两个字符串 S, T 相加 S + T 表示的是在 S 后紧挨着写下 T 得到的长度为 |S | + |T|的字符串。

【题目描述】

现有一个字符串 S。 Tiffany 将从中划出 na 个子串作为 A 类串，第 i 个（1 ≤ i ≤ a）为 Ai = S (lai,rai)。

类似地，Yazid 将划出 nb 个子串作为 B 类串，第 i 个（1 ≤ i ≤ b）为 Bi = S (lbi,rbi)。

现额外给定 m 组支配关系，每组支配关系 (x, y) 描述了第 x 个 A 类串支. 配. 第 y 个B 类串。 求一个长. 度. 最. 大. 的目标串 T，使得存在一个串 T 的分割 T = t1 +t2 +· · ·+tk（k ≥ 0）

满足： • 分割中的每个串 ti 均为 A 类串：即存在一个与其相等的 A 类串，不妨假设其为ti = Aidi。 • 对于分割中所有相邻的串 ti, ti+1（1 ≤ i < k），都有存在一个 Aidi 支配的 B 类串，使得该 B 类串为 ti+1 的前缀。

方便起见，你只需要输出这个最大的长度即可。 特别地，如果存在无限长的目标串（即对于任意一个正整数 n，都存在一个满足限制的长度超过 n 的串），请输出 −1。

【输入格式】

从文件 string.in 中读入数据。

单个测试点中包含多组数据，输入的第一行包含一个非负整数 T 表示数据组数。

接下来依次描述每组数据，对于每组数据：

第 1 行一个只包含小写字母的字符串 S。

第 2 行一个非负整数 na，表示 A 类串的数目。接下来 na 行，每行 2 个用空格隔开的整数。

– 这部分中第 i 行的两个数分别为 lai,rai，描述第 i 个 A 类串。

– 保证 1 ≤ lai ≤ rai ≤ |S |。

接下来一行一个非负整数 nb，表示 B 类串的数目。接下来 nb 行，每行 2 个用空格隔开的整数。

– 这部分中第 i 行的两个数分别为 lbi,rbi，描述第 i 个 B 类串。

– 保证 1 ≤ lbi ≤ rbi ≤ |S |。

• 接下来一行一个非负整数 m，表示支配关系的组数。接下来 m 行，每行 2 个用空格隔开的整数。

– 这部分中每行的两个整数 x, y，描述一对 (x, y) 的支配关系，具体意义见【题目描述】。

– 保证 1 ≤ x ≤ na，1 ≤ y ≤ nb。保证所有支配关系两两不同，即不存在两组支配关系的 x, y 均. 相同。

【输出格式】

输出到文件 string.out 中。依次输出每组数据的答案，对于每组数据：

• 一行一个整数表示最大串长。特别地，如果满足限制的串可以是无限长的，则请输出 −1。

【样例 1 输入】

3
abaaaba
2
4 7
1 3
1
3 4
1
2 1
abaaaba
2
4 7
1 3
1
7 7
1
2 1
abbaabbaab
4
1 5
4 7
6 9
8 10
3
1 6
10 10
4 6
5
1 2
1 3
2 1
3 3
4 1

【样例 1 输出】

7
-1
13

【样例 1 解释】

对于第 1 组数据，A 类串有 aaba 与 aba，B 类串有 aa，且 A2 支配 B1。我们可以找到串 abaaaba，它可以拆分成 A2 + A1，且 A1 包含由 A2 所支配的 B1 作为前缀。 可以证明不存在长度更大的满足限制的串。

对于第 2 组数据，与第 1 组数据唯一不同的是，唯一的 B 类串为 a。容易证明存在无限长的满足限制的串。

对于第 3 组数据，容易证明 abbaabbaaaabb 是最长的满足限制的串。

【样例 2】

见选手目录下的 string/string2.in 与 string/string2.ans。

【样例 3】

见选手目录下的 string/string3.in 与 string/string3.ans。

【样例 3 解释】

这个测试点满足【子任务】中提到的 |Ai| < |Bj | 的限制。

【子任务】

为了方便你的阅读，我们把测试点编号放在了表格的中间，请你注意这一点。

表格中的 |Ai|>|Bj| 指的是任意 B 类串的长度不超过任意 A 类串的长度。

对于所有测试点，保证：T≤100，且对于测试点内所有数据，|S|,na,nb,m的总和分别不会超过该测试点中对应的单组数据的限制的 10 倍。比如，对于第 1 组测试点，就有 ∑na≤10×100=1000等。特别地，我们规定对于测试点 4，有 T≤10。

对于所有测试点中的每一组数据，保证：1≤|S|≤2×10^5，na,nb≤2×10^5，m≤2×10^5。

【提示】

十二省联考命题组温馨提醒您：

数. 据. 千. 万. 条，. 清. 空. 第. 一. 条。.

多. 测. 不. 清. 空，. 爆. 零. 两. 行. 泪。.