07/04/2025 00:53:32

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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

Sample Output 1

cabc

Sample Input 2

Sample Output 2

zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

24/06/2010	Лето 2010 дорешивание (11C)
16/07/2010	Лето 2010 - 11 (C)