Problem C. Concatenation
Задачу добавил: elena
Успешно сдано решений: 4
Author: A. KleninInput file: input.txt
Output file: output.txt
Time limit: 2 sec
Memory limit: 64 Mb
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 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 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(a(N + j)) ≤ 2 × 10^9 for j = 1, M,
1 ≤ L ≤ R ≤ length(a(N + M)),
R − L + 1 ≤ 1000.
Sample tests
No. Sample input Sample output
1 2 2 3 6 cabc
a
bc
1 2
3 3
2 1 5 1 32 zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
z
1 1
2 2
3 3
4 4
5 5