1473. Concatenation

String concatenation is the operation of joining two character strings end to end. For example, the strings "foo" and "bar" may be concatenated to give "foobar".

You program will be given `N` strings `a_1,\ …,\ a_N` and will have to perform `M` concatenations represented by pairs of integers `(p_1,\ q_1),\ …,\ (p_M,\ q_M)`. Each pair `(p_j,\ q_j)` means that a new string `a_{N+j}` is the concatenation of strings `a_{p_j}` and `a_{q_j}`, where `1\ ≤\ p_j,\ q_j\ <\ N\ +\ j`.

For example, strings "a" and "bc" and pairs `(1,\ 2),\ (3,\ 3)` mean that new strings "abc" and "abcabc" are generated.

Your program must output a substring of `a_{N+M}` from position `L` to position `R`, counting from 1.

First line of input file contains integers `N\ M\ L\ R`. Following `N` lines contain strings `a_i` – one string per line. Each of the following `M` lines contain two integers `p_j\ q_j`.

Output file must contain a string of `R\ -\ L\ +\ 1` characters.

Constraints

`1\ ≤\ N\ ≤\ 1000`, `1\ ≤\ M\ ≤\ 1000`,

`1\ ≤\ "length"(a_i)\ ≤\ 1000` for `i\ =\ 1,\ N`, `1\ ≤\ "length"(a_{N+j})\ ≤\ 2*10^9` for `j\ =\ 1,\ M`,

`1\ ≤\ L\ ≤\ R\ ≤\ "length"(a_{N+M})`, `R\ -\ L\ +\ 1\ ≤\ 1000`.

2 2 3 6
a
bc
1 2
3 3

cabc

1 5 1 32
z
1 1
2 2
3 3
4 4
5 5

zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz