JOI est étudiant et se rend à l'université en bus. Son domicile et son université se trouvent dans la ville IOI. La ville compte $N$ arrêts de bus, numérotés de $1$ à $N$. L'arrêt le plus proche du domicile de JOI est l'arrêt $1$, et celui le plus proche de son université est l'arrêt $N$.

Il y a $M$ bus dans la ville IOI. Chaque bus part une fois par jour d'un arrêt donné à une heure donnée et arrive à un arrêt donné à une heure donnée. Aucun trajet ne se poursuit le jour suivant. JOI ne peut ni monter dans un bus ni en descendre en cours de trajet.

Chaque jour, JOI emprunte un ou plusieurs bus pour se rendre à l'université. Le temps nécessaire pour changer de bus est négligeable : pour prendre un bus partant d'un arrêt à une certaine heure, il suffit d'arriver à cet arrêt au plus tard à l'heure de départ. Il est également permis de passer plusieurs fois par le même arrêt.

Dans ces conditions, JOI souhaite savoir quand quitter son domicile pour arriver à l'université à temps pour les cours. L'heure du premier cours varie toutefois d'un jour à l'autre. Pour une période de $Q$ jours, on connaît chaque jour l'heure limite d'arrivée à l'arrêt $N$ permettant d'être à l'heure. Pour chaque jour, quelle est l'heure la plus tardive à laquelle JOI peut arriver à l'arrêt $1$ tout en étant à l'heure pour les cours ?

Tâche

On vous donne les informations sur les trajets des bus. Pour chacun de $Q$ jours, on vous donne également l'heure limite d'arrivée à l'arrêt $N$. Déterminez, dans chaque cas, l'heure la plus tardive à laquelle JOI peut arriver à l'arrêt $1$.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient deux entiers $N,M$, séparés par un espace, indiquant que la ville IOI compte $N$ arrêts et $M$ bus.
• La ligne $i$ ($1 \le i \le M$) parmi les $M$ lignes suivantes contient quatre entiers $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$), séparés par des espaces. Le bus $i$ part de l'arrêt $A_i$ à l'instant $X_i$ et arrive à l'arrêt $B_i$ à l'instant $Y_i$. Les instants sont exprimés en millisecondes écoulées depuis minuit.
• La ligne suivante contient un entier $Q$, le nombre de jours pour lesquels une heure limite d'arrivée à l'arrêt $N$ est donnée.
• La ligne $j$ ($1 \le j \le Q$) parmi les $Q$ lignes suivantes contient un entier $L_j$. Le jour $j$, JOI doit arriver à l'arrêt $N$ au plus tard à l'instant $L_j$.

Sortie

Affichez $Q$ lignes sur la sortie standard. Sur la ligne $j$ ($1 \le j \le Q$), affichez un entier indiquant l'heure la plus tardive à laquelle JOI peut arriver à l'arrêt $1$ le jour $j$. S'il est impossible d'arriver à l'université à temps pour les cours, affichez $-1$.

Contraintes

Toutes les données d'entrée respectent les conditions suivantes.

• $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$), pour $1 \le i \le M$.
• $1 \le Q \le 100\,000$.
• $0 \le L_j < 86\,400\,000$ ($=24\times60\times60\times1000$), pour $1 \le j \le Q$.

Sous-tâches

Sous-tâche 1 [20 points]

Les conditions suivantes sont respectées.

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

Sous-tâche 2 [15 points]

Les conditions suivantes sont respectées.

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

Sous-tâche 3 [15 points]

• $Q=1$.

Sous-tâche 4 [50 points]

Il n'y a pas de contrainte supplémentaire.

Exemples

Entrée 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

Sortie 1

-1
5
10
30

Remarque

Il est impossible d'arriver à l'arrêt $5$ au plus tard à l'instant $10$.

Pour arriver au plus tard à l'instant $30$, il suffit de prendre le quatrième bus à l'instant $5$.

Pour arriver au plus tard à l'instant $60$, on peut procéder ainsi.

• Prendre le premier bus à l'instant $10$.
• Arriver à l'arrêt $2$ à l'instant $25$, attendre $1$ milliseconde, puis prendre le troisième bus.
• Arriver à l'arrêt $5$ à l'instant $50$.

Pour arriver au plus tard à l'instant $100$, on peut procéder ainsi.

• Prendre le cinquième bus à l'instant $30$.
• Arriver à l'arrêt $4$ à l'instant $40$, attendre $10$ millisecondes, puis prendre le sixième bus.
• Arriver à l'arrêt $5$ à l'instant $70$.

Entrée 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

Sortie 2

0
0
0
1
1
2