Осенний турнир 2016

Problem C. Concatenation ≡

problems
visible spaces
basic formulae
wide text
editor

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 a₁, …, a_N and will have to perform M concatenations represented by pairs of integers (p₁, q₁), …, (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.

Input file format

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 format

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⁹ for j = 1, M,

1 ≤ L ≤ R ≤ length(a_N + 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`