Description

Yazid and Tiffany like string problems. Here, we will introduce some basic concepts about strings.

For a string $S$, we define $|S|$ as the length of $S$.

Next, we define the substring $S(L, R)$ as the string formed by concatenating the characters of $S$ from the $L$-th character to the $R$-th character (counting from left to right). Specifically, if $L < 1$, $R > |S|$, or $L > R$, then $S(L, R)$ represents an empty string.

We say two strings are equal if and only if they have the same length and the characters at each position from left to right are identical.

We say a string $T$ is a prefix of $S$ if and only if $S(1, |T|) = T$.

The concatenation of two strings $S$ and $T$, denoted as $S + T$, is a string of length $|S| + |T|$ formed by writing $T$ immediately after $S$.

There is a string $S$.

Tiffany will select $n_a$ substrings from $S$ as type-A strings, where the $i$-th ($1 \le i \le n_a$) is $A_i = S(l_{a_i}, r_{a_i})$.

Similarly, Yazid will select $n_b$ substrings from $S$ as type-B strings, where the $i$-th ($1 \le i \le n_b$) is $B_i = S(l_{b_i}, r_{b_i})$.

Additionally, $m$ dominance relations are given, where each relation $(x, y)$ describes that the $x$-th type-A string dominates the $y$-th type-B string.

Find a target string $T$ of maximum length such that there exists a partition $T = t_1 + t_2 + \dots + t_k$ ($k \ge 0$) satisfying:

• Each string $t_i$ in the partition is a type-A string: that is, there exists a type-A string equal to it; let's assume $t_i = A_{id_i}$.
• For all adjacent strings $t_i, t_{i+1}$ ($1 \le i < k$) in the partition, there exists a type-B string dominated by $A_{id_i}$ such that this type-B string is a prefix of $t_{i+1}$.

For convenience, you only need to output this maximum length.

Specifically, if there exists an infinitely long target string (i.e., for any positive integer $n$, there exists a string satisfying the constraints with length greater than $n$), please output $-1$.

Input

The input is read from the file string.in.

A single test case contains multiple datasets. The first line of the input contains a non-negative integer $T$ representing the number of datasets.

The datasets follow sequentially. For each dataset:

• The first line contains a string $S$ consisting only of lowercase letters.
• The second line contains a non-negative integer $n_a$, representing the number of type-A strings. The next $n_a$ lines each contain 2 space-separated integers.
  • The two integers in the $i$-th line of this part are $l_{a_i}, r_{a_i}$, describing the $i$-th type-A string.
  • It is guaranteed that $1 \le l_{a_i} \le r_{a_i} \le |S|$.
• The next line contains a non-negative integer $n_b$, representing the number of type-B strings. The next $n_b$ lines each contain 2 space-separated integers.
  • The two integers in the $i$-th line of this part are $l_{b_i}, r_{b_i}$, describing the $i$-th type-B string.
  • It is guaranteed that $1 \le l_{b_i} \le r_{b_i} \le |S|$.
• The next line contains a non-negative integer $m$, representing the number of dominance relations. The next $m$ lines each contain 2 space-separated integers.
  • The two integers $x, y$ in each line of this part describe a dominance relation $(x, y)$, the specific meaning of which is defined in the Description.
  • It is guaranteed that $1 \le x \le n_a$ and $1 \le y \le n_b$. It is guaranteed that all dominance relations are distinct, i.e., there are no two identical pairs $(x, y)$.

Output

Output to the file string.out.

Output the answer for each dataset sequentially. For each dataset:

• Output a single integer representing the maximum string length. Specifically, if the string satisfying the constraints can be infinitely long, please output $-1$.

Examples

Input 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

Output 1

7
-1
13

Note

For the first dataset, the type-A strings are aaba and aba, and the type-B string is aa, with $A_2$ dominating $B_1$. We can find the string abaaaba, which can be split into $A_2 + A_1$, and $A_1$ contains $B_1$ (which is dominated by $A_2$) as a prefix. It can be proven that no longer string satisfying the constraints exists.

For the second dataset, the only difference from the first dataset is that the only type-B string is a. It is easy to prove that an infinitely long string satisfying the constraints exists.

For the third dataset, it is easy to prove that abbaabbaaaabb is the longest string satisfying the constraints.

Subtasks

For all test cases, it is guaranteed that $T \le 100$, and for all data within a test case, the sum of $|S|, n_a, n_b, m$ will not exceed 10 times the limit of a single dataset in that test case. For example, for the first test case, $\sum n_a \le 10 \times 100 = 1000$, etc. Specifically, we specify that for test case 4, $T \le 10$.

For every dataset in all test cases, it is guaranteed that $1 \le |S| \le 2 \times 10^5$, $n_a, n_b \le 2 \times 10^5$, and $m \le 2 \times 10^5$.