printРабочее место участника

printЗадачи

1473. Concatenation

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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.
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^9` for `j\ =\ 1,\ M`,
`1\ ≤\ L\ ≤\ R\ ≤\ "length"(a_{N+M})`, `R\ -\ L\ +\ 1\ ≤\ 1000`.

Sample Input 1

2 2 3 6
a
bc
1 2
3 3

Sample Output 1

cabc

Sample Input 2

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

Sample Output 2

zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz
Source: NEERC ICPC, Far Eastern subregion, 2008
loading