B. Speedrun Splits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Tanner is speedrunning the hit video game The Legend of Zelda: Tears of the Kingdom, where his goal is to beat the game as fast as possible. To keep track of his progress, he creates splits for each important objective in the run.

Tanner wants to know his improvement between runs for certain splits. Given $$$N$$$ different runs composed of $$$K$$$ splits, with $$$t_i$$$ being the time in seconds for each split, for each of $$$Q$$$ different queries for a certain split $$$s$$$, please output the maximum improvement between any two times for a given split.

Input

Line $$$1$$$: Three space separated integers $$$N$$$,$$$K$$$,$$$Q$$$

Lines $$$2…N+1$$$: $$$K$$$ space separated integers $$$t_1...t_K$$$

Lines $$$N+2…N+Q+1$$$: An integer, $$$s$$$

Output

Lines $$$1…Q$$$: An integer representing the maximum improvement between any two times for split $$$s$$$.

Example
Input
4 5 3
1 3 4 6 9
2 4 5 7 8
1 2 6 9 10
1 2 3 4 7
2
4
1
Output
2
5
1
Note

$$$1 \lt N,K ≤700$$$

$$$1≤t_i≤10^9, t_i \lt t_i+1$$$

$$$1≤Q≤10^5$$$

$$$1≤s≤K$$$

For the second split, the maximum improvement is either between runs 2 and 3 or between runs 2 and 4, which results in an improvement of 4-2=2 seconds.

For the fourth split, the maximum improvement is between runs 3 and 4, which results in an improvement of 9-4=5 seconds.

For the first split, the maximum improvement is between either runs 1 and 2, between runs 2 and 3, or between runs 2 and 4, which results in an improvement of 2-1=1 second.