19849번 - 문제지 나르기

문제

교준이는 온라인으로 진행되는 SNUPC 2020에 아쉬움이 남아, $N$명의 대회 참가자들의 집으로 문제지를 직접 배달해주기로 했다.

여러분이 익히 알고 있듯 이 우주는 11차원이기 때문에, 참가자들의 집은 11차원 좌표의 한 점 $\mathbf{x} = (x_{1}, x_{2}, \cdots, x_{11})$로 나타낼 수 있다. 이 우주에서 이동하기 위해서는 좌표축을 따라 나 있는 도로를 타고 이동해야 하기 때문에, 두 점 $\mathbf{x},ドル $\mathbf{y}$ 사이를 이동하는 데 필요한 거리는 아래와 같다.

$$ \mathrm{dist}(\mathbf{x},\mathbf{y}) = \sum_{k=1}^{11} \lvert x_{k} - y_{k} \rvert $$

교준이는 문제지를 실은 차를 한 곳에 주차해둔 뒤 문제지를 나를 것이다. 11차원 세계에는 $Q$개의 주차장이 있고, 주차장 역시 11차원 좌표계의 한 점 $\mathbf{y} = (y_{1}, \cdots, y_{11})$으로 나타낼 수 있다.

문제지를 직접 들고 나르는 일은 힘들기 때문에, 교준이는 각 주차장의 위치에 대해 가장 멀리 떨어진 참가자의 집까지 거리를 알고 싶어한다. 교준이는 이 문제가 나쁘지 않다고 생각했는지, 문제지에 이 문제까지 적어서 여러분에게 가져다주려고 한다.

입력

입력의 첫째 줄에는 참가자의 수 $N,ドル 주차장의 수 $Q$가 공백을 사이에 두고 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 각 참가자의 집 좌표 $(x_{i,1}, \cdots, x_{i,11})$가 주어진다. 구체적으로, $(i+1)$번째 줄에는 $i$번째 참가자의 집 좌표를 나타내는 11ドル$개의 정수 $x_{i,1},ドル $\cdots,ドル $x_{i,11}$가 공백을 사이에 두고 주어진다.

$N+2$번째 줄부터 $Q$개의 줄에 걸쳐 주차장의 좌표 $(y_{i,1}, \cdots, y_{i,11})$가 주어진다. 구체적으로, $(N+1+i)$번째 줄에는 $i$번째 주차장의 집 좌표를 나타내는 11ドル$개의 정수 $y_{i,1},ドル $\cdots,ドル $y_{i,11}$가 공백을 사이에 두고 주어진다.

출력

$Q$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $i$번째 주차장과 가장 멀리 떨어진 참가자의 집까지 거리를 출력한다.

제한

• 1ドル \le N, Q \le 50,000$
• $-10^{9} \le x_{i, j}, y_{i, j} \le 10^{9}$$(1 \le i \le N, 1 \le j \le 11)$

힌트