Author: | A. Klenin | Time limit: | 2 sec | |
Input file: | input.txt | Memory limit: | 64 Mb | |
Output file: | output.txt |
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.
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.
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|