İlim and Skr are coworkers working at Computer Club Inc. They work in the same building but in different rooms. İlim works in the room numbered with \(\mathbf{N}\) and Skr works in the room numbered with \(1\).

Each day Skr visits İlim during his break. There are \(\mathbf{Q}\) days and his break on \(i^{th}\) day starts on \(\mathbf{{D_i}^{th}}\) minute. He wants to know the fastest time he would arrive at İlim's room.

Skr needs to go through some doors in the Computer Club Inc. Each door connects to different rooms. However, in Computer Club Inc. all of the doors are revolving doors, and one can only enter them at the start of each period \(\mathbf{P_i}\). For example, if \(\mathbf{P_i} = 3\) the \(i^{th}\) door is only enterable on \(\{0, 3, 6, 9...\}\).

Input

In the first line, integers \(\mathbf{N}\), and \(\mathbf{M}\), and \(\mathbf{Q}\) are given. The number of rooms, the number of doors, and the number of break times Skr has.

In each of the following \(\mathbf{M}\) lines represent the \(\mathbf{M}\) doors. They include \(\mathbf{A_i}\), \(\mathbf{B_i}\) (The rooms they connect), and \(\mathbf{P_i}\) (The period it revolves).

In the last line, there are \(\mathbf{Q}\) integers. Each \(\mathbf{D_i}\) on this line represents the Skr's break time on \(i^{th}\) day.

• \(1 \leq \mathbf{N} \leq 10^4\)
• \(1 \leq \mathbf{M} \leq 3 \cdot 10^4\)
• \(1 \leq \mathbf{Q} \leq 10^2\)
• \(1 \leq \mathbf{A_i}, \mathbf{B_i} \leq \mathbf{N}\)
• \(2 \leq \mathbf{P_i} \leq 10^3\)
• \(0 \leq \mathbf{D_i} \leq 10^3\)

Output

The fastest time Skr would reach İlim's room \(\mathbf{N}\) for each of the \(\mathbf{Q}\) starting times in separate lines. If there are no paths, print -1.

Examples

Input 1:

4 3 2
1 2 3
2 3 2
3 4 7
0 10

Output 1:

8
22

Input 2:

4 4 4
1 2 4
2 3 74
3 4 47
2 4 7
15 5 2 3

Output 2:

22
15
8
8

Explanation

Input 1

• First starting time:

  • At \(0^{th}\) minute, Skr passes on the door between rooms 1 and 2. Skr arrives in room 2 at \(1^{st}\) minute. (All doors are open at \(0^{th}\) minute)
  • Skr waits one minute (2 - 1 = 1) till the door between rooms 2 and 3 is open. Then he passes that door at \(2^{nd}\) minute and, arrives in room 3 at \(3^{rd}\) minute.
  • Skr waits four minutes (7 - 3 = 4) till the door between rooms 3 and 4 is open. Then he passes that door at \(7^{th}\) minute and, Skr arrives in room 4 a \(8^{th}\) minute.

• Second starting time:

  • Skr waits for 2 minutes (12 - 10 = 2) till the door between rooms 1 and 2 is open. Then he passes that door at \(12^{th}\) minute and, arrives in room 2 at \(13^{th}\) minute.
  • Skr waits for 1 minute (14 - 13 = 1) till the door between rooms 2 and 3 is open. Then he passes that door at \(14^{th}\) minute and, arrives in room 3 at \(15^{th}\) minute.
  • Skr waits for 6 minutes (21 - 15 = 6) till the door between rooms 3 and 4 is open. Then he passes that door at \(21^{st}\) minute and, arrives in room 4 at \(22^{nd}\) minute.