(Problem C ) Error Sequence
Tag(s):

## Algorithms, Medium, String, Suffix Automata

Problem
Editorial
Analytics

Consider a strictly-increasing sequence of integers $a_1, a_2, \dots, a_k$. Alice picked a continuous sequence $p_1, p_2, \dots, p_n$ from it.

Bob then removed exactly $n-m$ numbers from this sequence, while maintaining the relative order of the remaining elements, thus obtaining a sequence $q_1, q_2, \dots, q_m$. He then subtracted $q_1$ from all the elements to form the final sequence $b_1, b_2, \dots, b_m$.

For example, let $\{a_i\} = \{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31\}, p_1 = 11, n = 6, m = 4$. This yields the sequence of primes $p=\{11, 13, 17, 19, 23, 29\}$. Assume that Bob has removed the numbers 17 and 23 to obtain $q=\{11, 17, 19, 29\}$. After that, he subtracted 11 from every element to get $b=\{0, 6, 8, 18\}$.

Alternatively, he could have removed 11 and 29 to obtain the sequence $q = \{13, 17, 19, 23\}$ and $b = \{0, 4, 6, 10\}$. Note that the same sequence may also be generated by, for instance, picking $p = \{13, 17, 19, 23, 29, 31\}$ and removing 29 and 31.

Eve found the number $n$ and the sequences $\{a_i\}_{i=1}^{k}$$\{b_i\}_{i=1}^{m}$. She now wonders, what is the smallest possible $p_1$, that could yield the sequence $\{b_i\}_{i=1}^{m}$ through the process described above?

Input format:

• First line: $t$ (number of test cases)
• For each test case
• First line: Three space-separated integers $k$$n$and $m$ satisfying $1 \leq m \leq n \leq k$
• Second line: $k$ space-separated integers $\{a_i\}_{i=1}^k$ satisfying $0 \leq a_i \leq 10^9$ and $a_i < a_{i+1}$
• Third line: $m$ space-separated integers $\{b_i\}_{i=1}^m$. It is guaranteed that $b_1 = 0$ .

It is guaranteed that there always exists a solution.

Output:

For each test case, output a single integer $p_1$ - the smallest element in the sequence that Alice chose.

Scoring:

In all test sets, $1 \leq t \leq 10$.

In the first test set, worth 12 points, $1 \leq m = n \leq 10^2$ and $k \leq 10^4$.

In the second test set, worth 21 points, $1 \leq m < n \leq 10^2$ and $k \leq 10^4$.

In the third test set, worth 24 points, $1 \leq m = n \leq 10^5$ and $k \leq 2*10^5$.

In the fourth test set, worth 25 points, $1 \leq m \leq n \leq 10^5$$n - m \leq 50$ and $k \leq 2*10^5$.

In the fifth test set, worth 18 points,$t=3$$1 \leq m \leq n \leq 5*10^5$$n - m \leq 100$ and $k \leq 10^6$.

SAMPLE INPUT
1
11 6 4
2 3 5 7 11 13 17 19 23 29 31
0 6 8 18

SAMPLE OUTPUT
11

Explanation

This is the example from the statement.

Time Limit: 5,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

HourStorm #3

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
Уведомления

?