Problem C. Concatenation

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

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 a1, …, aN and will have to perform M concatenations represented by pairs of integers (p1, q1), …, (pM, qM). Each pair (pj, qj) means that a new string aN + j is the concatenation of strings apj and aqj, where 1 ≤ pj, qj < 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 aN + M from position L to position R, counting from 1.

Input file format

First line of input file contains integers N M L R. Following N lines contain strings ai — one string per line. Each of the following M lines contain two integers pj qj.

Output file format

Output file must contain a string of R − L + 1 characters.

Constraints

1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000,

1 ≤ length(ai) ≤ 1000 for i = 1, N,

1 ≤ length(aN + j) ≤ 2 × 109 for j = 1, M,

1 ≤ L ≤ R ≤ length(aN + M),

R − L + 1 ≤ 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 2 3 6
a
bc
1 2
3 3
cabc
2
1 5 1 32
z
1 1
2 2
3 3
4 4
5 5
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

0.079s 0.012s 13