Alien_Homophones (OOI qualification)
Time limit: 2 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: aho-corasick, lowest common ancestor, hash map, union-find

# Alien Homophones

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 2 seconds       |
| Memory limit: | 1024 megabytes  |

Okarun is obsessed with the idea that aliens exist. In his childhood, he tried various ways to contact them, but to no avail. This is not surprising, as aliens speak a completely different language! One day, he stumbled upon an article stating that aliens actually use lowercase Latin letters for writing, but read words in a completely different way.

In the alien language, there is a set of $n + 26$ different sounds, each represented by a string of Latin letters $s_i$. It is known that for any $1 \le i \le 26$, the $i$-th sound is represented by a string of length one, consisting of the $i$-th letter of the Latin alphabet. For any $i > 26$, the sound with number $i$ is represented by a string consisting of at least two Latin letters.

When an alien wants to read the word $x$, he starts reading it from the first position. When the alien is at position $i$, he looks for a sound $s_j$ in the set of sounds such that it appears as a substring† in $x$, starting from position $i$. If there are multiple such sounds, he chooses the sound $s_j$ with the maximum length. Then he pronounces that sound and moves to position $i + |s_j|$ and continues reading the word until he has read it completely. Note that we can always read any word because all Latin letters are sounds.

It also turned out that some alien sounds actually sound the same but are written differently. This means that there are some pairs of sound strings $s_i$ and $s_j$ ($i \ne j$) such that $s_i \ne s_j$, but the sounds represented by these strings are the same. Note that if $s_i$ and $s_j$ are considered the same sound, and $s_j$ and $s_l$ are considered the same sound, then $s_i$ and $s_l$ are also considered the same sound.

Aliens call some words homophones — words that sound the same, and their spelling may either match or differ. In other words, if we have two words $v$ and $w$, aliens call them homophones if the sequence of sounds pronounced by aliens while reading word $v$ matches the sequence of sounds pronounced by aliens while reading word $w$.

Okarun wrote some text $t$, consisting of lowercase Latin letters. At one point, he became interested in examining $q$ pairs of substrings of the text. In each such pair of substrings, the first substring is from the $a_i$-th to the $b_i$-th character in the text $t$, inclusive, and the second is from the $c_i$-th to the $d_i$-th characters in the text $t$, inclusive. For each pair of substrings, Okarun wants to know if these substrings are homophones when read as words in the alien language.

† A substring of a string $s$ is a string that can be obtained by removing some number of characters (possibly zero) from the beginning of the string $s$ and some number of characters (possibly zero) from the end of the string $s$.

### Input

The first line contains a non-empty string $t$ ($1 \le |t| \le 500\,000$), consisting of lowercase Latin letters — the text written by Okarun.

The second line contains two integers $n$ and $k$ ($0 \le n \le 500\,000$, $0 \le k < n + 26$) — the number of sounds in the set that have a length of at least two and the number of pairs of identical sounds noted by Okarun.

The next $n$ lines describe the sounds numbered from the 27th. The $i$-th of them contains a non-empty string $s_{i+26}$ ($2 \le |s_{i+26}| \le 10^6$), consisting of lowercase Latin letters — the representation of the $(i+26)$-th sound. It is guaranteed that all sound strings are different. Note that there are no strings from `"a"` to `"z"` in the input; however, in each test, they are considered sounds numbered from 1 to 26.

The next $k$ lines describe pairs of identical sounds originally noted by Okarun. Each of them contains a pair of integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n + 26$; $x_i \ne y_i$) — a pair of sound numbers that Okarun considers identical in sound. It is guaranteed that each pair of numbers appears no more than once. Note that the equality of some other pairs of sounds may follow from this set.

The next line contains a single integer $q$ ($1 \le q \le 300\,000$) — the number of queries for pairs of substrings of the text, for which it is necessary to determine whether they are alien homophones.

In the next $q$ lines, the $i$-th of them contains four integers $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|$), which specify the substrings of the text — the first substring from position $a_i$ to position $b_i$ (inclusive) in the text $t$, the second from position $c_i$ to position $d_i$ (inclusive) in the text $t$.

Let $S$ denote the sum of the lengths of the sounds $\sum |s_i|$ (excluding the sounds `"a"` to `"z"`). It is guaranteed that $S \le 10^6$.

### Output

Output $q$ lines. If the pair of strings from the $i$-th query are identical in sound, output `"Yes"` (without quotes) in the $i$-th line; otherwise, output `"No"` (without quotes) in the $i$-th line.

### Example

| standard input | standard output |
|----------------|-----------------|
| abracadabra    | Yes             |
| 2 3            | Yes             |
| cada           | No              |
| ca             | Yes             |
| 1 27           |                 |
| 1 28           |                 |
| 1 4            |                 |
| 4              |                 |
| 5 11 1 4       |                 |
| 4 6 5 7        |                 |
| 5 7 5 8        |                 |
| 2 5 2 5        |                 |

### Note

In the first query:

- The first substring `cadabra` is read as sounds: cada, b, r, a;
- The second substring `abra` is read as sounds: a, b, r, a.

The sounds `cada` and `a` are noted as identical (pair (1, 27)), therefore these two substrings are alien homophones.

In the second query:

- The first substring `aca` is read as sounds: a, ca;
- The second substring `cad` is read as sounds: ca, d.

The sounds `a` and `ca` are noted as identical (pair (1, 28)), the sounds `ca` and `d` are also identical (since the sounds with numbers (1, 4) and (1, 28) are identical, then the sounds with numbers 4 and 28 are also identical), therefore these two substrings are also alien homophones.

In the third query:

- The first substring `cad` is read as sounds: ca, d;
- The second substring `cada` is read as sounds: cada.

The number of sounds does not match, so these two substrings are definitely not alien homophones.

In the fourth query, two identical substrings are given, so they are read the same and are alien homophones.

## Scoring

The tests for this problem consist of ten groups. Points for each group are awarded only if all tests of the group and all tests of some of the previous groups are passed. Note that passing the samples is not required for some groups. Offline-testing means that the results of testing your solution on this group will only be available after the competition ends.

| Group | Points | |t| | S | q | Required groups | Comment |
|---|---|---|---|---|---|---|---|
| 0 | 0 |  | – | – | – | – | Samples. |
| 1 | 8 |  | |t| ≤ 500 | | S ≤ 500 | | q ≤ 500 | 0 |  |
| 2 | 7 |  | |t| ≤ 6 000 | | S ≤ 6 000 | | q ≤ 6 000 | – | $b_i = d_i = |t|$ |
| 3 | 9 |  | |t| ≤ 6 000 | | S ≤ 6 000 | | q ≤ 200 000 | 2 | $b_i = d_i = |t|$ |
| 4 | 15 |  | |t| ≤ 200 000 | | S ≤ 200 000 | | q ≤ 200 000 | 2, 3 | $b_i = d_i = |t|$ |
| 5 | 8 |  | |t| ≤ 6 000 | | S ≤ 6 000 | | q ≤ 200 000 | – | $a_i = c_i = 1$ |
| 6 | 6 |  | |t| ≤ 500 | | S ≤ 500 | | q ≤ 200 000 | 0, 1 |  |
| 7 | 7 |  | |t| ≤ 6 000 | | S ≤ 6 000 | | q ≤ 6 000 | 0 – 2 |  |
| 8 | 10 |  | |t| ≤ 6 000 | | S ≤ 200 000 | | q ≤ 6 000 | 0 – 2, 7 |  |
| 9 | 19 |  | |t| ≤ 200 000 | | S ≤ 400 000 | | q ≤ 200 000 | 0 – 8 |  |
| 10 | 11 |  | – | – | – | 0 – 9 | Offline-testing. |

Starter code:

Grader code:

Setup script:

Evaluation script: