O universitário JOI vai de ônibus para a universidade. Tanto sua casa quanto a universidade ficam na cidade de IOI. A cidade possui $N$ pontos de ônibus, numerados de $1$ a $N$. O ponto mais próximo da casa de JOI é o ponto $1$, e o mais próximo da universidade é o ponto $N$.

Há $M$ ônibus circulando na cidade. Cada um parte uma vez por dia de um ponto determinado, em um horário determinado, e chega a um ponto determinado em outro horário determinado. Nenhum ônibus faz uma viagem que atravesse a meia-noite. JOI não pode embarcar nem desembarcar no meio de uma viagem de ônibus.

Todos os dias, JOI chega à universidade usando um ou mais ônibus. O tempo necessário para trocar de ônibus pode ser desprezado. Isto é, para embarcar em um ônibus que parte de certo ponto em certo horário, basta chegar a esse ponto até o horário de partida, inclusive. Também é permitido usar o mesmo ponto várias vezes.

Nessas condições, JOI quer saber quando deve sair de casa para chegar à universidade a tempo para a aula. Porém, o horário de início da primeira aula varia de um dia para outro. Para um período de $Q$ dias, sabe-se até que horário ele deve chegar ao ponto $N$ para não se atrasar em cada dia. Para cada dia, qual é o horário mais tardio em que JOI pode chegar ao ponto $1$ e ainda chegar a tempo para a aula?

Tarefa

São fornecidas informações sobre as viagens dos ônibus. Também são fornecidos, para $Q$ dias, os horários-limite de chegada ao ponto $N$. Para cada um deles, determine o horário mais tardio em que JOI pode chegar ao ponto $1$.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha contém dois inteiros $N,M$, separados por um espaço, indicando que existem $N$ pontos e $M$ ônibus na cidade de IOI.
• A $i$-ésima linha ($1 \le i \le M$) das próximas $M$ linhas contém quatro inteiros $A_i,B_i,X_i,Y_i$ ($1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$), separados por espaços. Isso indica que o $i$-ésimo ônibus parte do ponto $A_i$ no instante $X_i$ e chega ao ponto $B_i$ no instante $Y_i$. Os instantes são expressos em milissegundos decorridos desde exatamente a meia-noite.
• A linha seguinte contém um inteiro $Q$, indicando a quantidade de dias para os quais são fornecidos horários-limite de chegada ao ponto $N$.
• A $j$-ésima linha ($1 \le j \le Q$) das próximas $Q$ linhas contém um inteiro $L_j$, indicando que, no $j$-ésimo dia, é necessário chegar ao ponto $N$ até o instante $L_j$.

Saída

Escreva $Q$ linhas na saída padrão. Na $j$-ésima linha ($1 \le j \le Q$), escreva um inteiro que represente o horário mais tardio em que JOI pode chegar ao ponto $1$ no $j$-ésimo dia. Se for impossível chegar à universidade a tempo para a aula, escreva -1.

Restrições

Todos os dados de entrada satisfazem as condições a seguir.

• $2 \le N \le 100\,000$.
• $1 \le M \le 300\,000$.
• $0 \le X_i < Y_i < 86\,400\,000\ (=24\times60\times60\times1000)$ ($1 \le i \le M$).
• $1 \le Q \le 100\,000$.
• $0 \le L_j < 86\,400\,000\ (=24\times60\times60\times1000)$ ($1 \le j \le Q$).

Subtarefas

Subtarefa 1 [20 pontos]

As seguintes condições são satisfeitas.

• $N \le 2\,000$.
• $M \le 2\,000$.
• $Q=1$.

Subtarefa 2 [15 pontos]

As seguintes condições são satisfeitas.

• $N \le 2\,000$.
• $M \le 2\,000$.

Subtarefa 3 [15 pontos]

• $Q=1$.

Subtarefa 4 [50 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

5 6
1 2 10 25
1 2 12 30
2 5 26 50
1 5 5 20
1 4 30 40
4 5 50 70
4
10
30
60
100

Saída 1

-1
5
10
30

Observação

Não é possível chegar ao ponto $5$ até o instante $10$.

Para chegar até o instante $30$, basta embarcar no quarto ônibus no instante $5$.

Para chegar até o instante $60$, pode-se fazer o seguinte:

• Embarcar no primeiro ônibus no instante $10$.
• Chegar ao ponto $2$ no instante $25$, esperar 1 milissegundo e embarcar no terceiro ônibus.
• Chegar ao ponto $5$ no instante $50$.

Para chegar até o instante $100$, pode-se fazer o seguinte:

• Embarcar no quinto ônibus no instante $30$.
• Chegar ao ponto $4$ no instante $40$, esperar 10 milissegundos e embarcar no sexto ônibus.
• Chegar ao ponto $5$ no instante $70$.

Entrada 2

3 8
1 2 1 5
1 3 0 1
1 3 2 8
2 3 2 3
2 3 3 4
2 3 4 5
2 3 5 6
2 3 6 7
6
3
4
5
6
7
8

Saída 2

0
0
0
1
1
2