Speedrun Splits
Description
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.
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$
Lines $1…Q$: An integer representing the maximum improvement between any two times for split $s$.
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$.
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
2
5
1
Note
$1<N,K ≤700$
$1≤t_i≤10^9, t_i<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.