Delivering Problem Sheets

Gyo-jun felt unsatisfied with the online SNUPC 2020, so he decided to deliver the problem sheets directly to the homes of the $N$ contest participants.

As you know, this universe has 11 dimensions, so a participant's home is a point in 11-dimensional coordinates, $\mathbf{x} = (x_{1}, x_{2}, \cdots, x_{11})$. To move around in this universe you have to use the roads that run along the coordinate axes, so the distance needed to travel between two points $\mathbf{x}$ and $\mathbf{y}$ is as follows.

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

Gyo-jun will park the car carrying the problem sheets in one place and then deliver them. The 11-dimensional world has $Q$ parking lots, and a parking lot is also a point in the 11-dimensional coordinate system, $\mathbf{y} = (y_{1}, \cdots, y_{11})$.

Carrying the problem sheets by hand is hard, so for each parking lot location Gyo-jun wants to know the distance to the farthest participant's home. He thought this problem was not bad, so he is going to write it on the problem sheet too and bring it to you.

The first line of the input gives the number of participants $N$ and the number of parking lots $Q$, separated by a space.

Each of the next $N$ lines gives the coordinates of a participant's home, $(x_{i,1}, \cdots, x_{i,11})$. Specifically, line $(i+1)$ gives the $11$ integers $x_{i,1}$, $\cdots$, $x_{i,11}$ that represent the coordinates of participant $i$'s home, separated by spaces.

Each of the $Q$ lines starting from line $N+2$ gives the coordinates of a parking lot, $(y_{i,1}, \cdots, y_{i,11})$. Specifically, line $(N+1+i)$ gives the $11$ integers $y_{i,1}$, $\cdots$, $y_{i,11}$ that represent the coordinates of parking lot $i$, separated by spaces.

Print the answers over $Q$ lines. On line $i$, print the distance from parking lot $i$ to the farthest participant's home.

• $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)$