Resgatando robôs
Problem
Uma tempestade de pó de diamante surgiu no planeta de Shelezyak. Como você sabe, o pó de diamante causa paralisia em robôs. No início da tempestade, todos os robôs estavam ocupados trabalhando ao longo de uma estrada reta. Há m oficinas de reparo ao longo da mesma estrada. Portanto, decidiu-se enviar cada robô à oficina mais próxima para renovar seu lubrificante.
É necessário que cada robô determine a oficina mais próxima a ele.
Entrada
A primeira linha contém o número
n - o número de robôs(
\(1 <= n <= 100000\)). A segunda linha contém
n inteiros diferentes, o
i-ésimo desses números especifica a distância desde o início da estrada até o local de trabalho do
i-th robô . A terceira linha da entrada contém o número
m - o número de oficinas (
1 <= m <= 100000). A quarta linha contém
m vários inteiros, o
iésimo desses números especifica a distância desde o início da estrada até o
ia oficina mecânica. Todas as distâncias são positivas e não excedem 109. O robô e a oficina podem estar localizados no mesmo ponto.
Impressão
Print n numbers - para cada robô, imprima o número da oficina mais próxima. As oficinas são numeradas de 1 a m na ordem em que são fornecidas na entrada.
Exemplos
| # |
Entrada |
Saída |
| 1 |
4
1 2 6 10
2
7 3
| 2 2 1 1 |