Problem Description

In the country of IOI, there are $ N $ towns numbered from $ 1 $ to $ N $ and $ M $ roads numbered from $ 1 $ to $ M $.

Each road can only be traveled by taxi. Road $ i $ ($1 \leq i \leq M$) allows taxis to move bidirectionally between town $ A_i $ and town $ B_i $. The color of the taxi on road $ i $ is red if $ C_i = 1 $ and blue if $ C_i = 2 $. Taxis incur fees, and upon boarding, the amount of money you have changes as follows:

• Let the amount of money before boarding be $ a $ yen.
• If the taxi is red, the amount of money after boarding becomes $ a - 1 $ yen.
• If the taxi is blue, the amount of money after boarding becomes the integer part of $a \div 2$ yen.

You live in town $ 1 $ of the IOI country and want to know the answers to the following $ Q $ queries. The $ j $-th ($1 \leq j \leq Q$) query is as follows:

• Starting from town $ 1 $, what is the minimum amount of money you need to have initially to reach town $ T_j $ while having at least 1 yen left? If the answer is greater than $ L $ yen, output Large instead.

Given the information about the towns and taxis, and the queries, create a program that answers all the queries.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ Q $ $ L $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $\vdots$ $ A_M $ $ B_M $ $ C_M $ $ T_1 $ $ T_2 $ $\vdots$ $ T_Q $

Output Format

Output $ Q $ lines to the standard output. The $ j $-th line ($1 \leq j \leq Q$) should contain the answer to the $ j $-th query.

Sample Input and Output

Sample Input #1

7 6 1 10
1 2 2
2 3 1
3 4 2
4 5 1
5 6 1
6 7 2
5

Sample Output #1

10

Sample Input #2

10 9 3 25
1 2 2
2 3 1
3 4 1
4 5 1
5 6 2
6 7 1
7 8 1
8 9 1
9 10 2
10
9
3

Sample Output #2

Large
22
4

Sample Input #3

5 6 1 1000000000
1 4 1
1 5 1
4 5 1
3 4 1
3 5 1
2 3 1
2

Sample Output #3

4

Sample Input #4

9 11 5 10
1 2 1
1 3 2
2 3 2
2 9 2
3 9 1
4 9 1
8 9 1
5 8 1
5 7 1
4 7 2
6 7 2
2
6
7
8
9

Sample Output #4

2
Large
7
5
3

Notes/Hints

Constraints

• $2 \leq N \leq 200,000$.
• $N - 1 \leq M \leq 200,000$.
• $1 \leq Q \leq 200,000$.
• $1 \leq L \leq 1,000,000,000$.
• $1 \leq A_i < B_i \leq N$ ($1 \leq i \leq M$).
• $(A_i, B_i) \neq (A_j, B_j)$ ($1 \leq i < j \leq M$).
• $1 \leq C_i \leq 2$ ($1 \leq i \leq M$).
• $2 \leq T_j \leq N$ ($1 \leq j \leq Q$).
• Any town can be reached from any other town by traveling through some roads.
• All input values are integers.

Subtasks

1. ($ 9 $ points) $ M = N - 1 $, $ (A_i, B_i) = (i, i + 1) $ ($1 \leq i \leq M$), $ Q = 1 $, $N \leq 100$, $L \leq 100$.
2. ($ 19 $ points) $ M = N - 1 $, $ (A_i, B_i) = (i, i + 1) $ ($1 \leq i \leq M$), $ Q = 1 $.
3. ($ 19 $ points) $ M = N - 1 $, $ (A_i, B_i) = (i, i + 1) $ ($1 \leq i \leq M$).
4. ($ 16 $ points) $N \leq 50,000$, $M \leq 50,000$, $ Q = 1 $, $ C_i = 1 $ ($1 \leq i \leq M$).
5. ($ 20 $ points) $N \leq 50,000$, $M \leq 50,000$, $ Q = 1 $.
6. ($ 12 $ points) $N \leq 50,000$, $M \leq 50,000$, $Q \leq 50,000$.
7. ($ 5 $ points) No additional constraints.

Grading Notes

All submissions are graded on the judge system.

A submitted source code is considered correct for a subtask if it returns the correct result for all test inputs corresponding to that subtask.

The score for each submission is the sum of the points for the subtasks that the submitted source code is considered correct for.

The score for this task is the maximum score of all submissions for this task.

The current score can be checked from the "My Score Status" tab in the "Submission Results".

Sample Explanation 1

If you move along the path town $ 1 $ → town $ 2 $ → town $ 3 $ → town $ 4 $ → town $ 5 $, you will ride taxis of colors blue, red, blue, and red in order. Then, if you start with $ 10 $ yen, your money will change as $ 10 $ yen → $ 5 $ yen → $ 4 $ yen → $ 2 $ yen → $ 1 $ yen, and you can arrive at town $ 5 $ with at least $ 1 $ yen left. On the other hand, if you start with $ 9 $ yen or less, you cannot arrive at town $ 5 $ with at least $ 1 $ yen left. This input example satisfies the constraints of subtasks $ 1, 2, 3, 5, 6, 7 $.

Sample Explanation 2

For example, consider the first query. Starting from town $ 1 $ and moving to town $ 10 $, you will follow the path town $ 1 $ → town $ 2 $ → ... → town $ 9 $ → town $ 10 $. However, even if you start with $ L $ ( = $ 25 $) yen, your money will decrease as $ 25 $ yen → $ 12 $ yen → $ 11 $ yen → $ 10 $ yen → ... and you cannot arrive at town $ 10 $ with at least $ 1 $ yen left. Therefore, you must output Large. This input example satisfies the constraints of subtasks $ 3, 6, 7 $.

Sample Explanation 3

If you move along the path town $ 1 $ → town $ 5 $ → town $ 3 $ → town $ 2 $, you will ride red taxis three times. Then, if you start with $ 4 $ yen, your money will change as $ 4 $ yen → $ 3 $ yen → $ 2 $ yen → $ 1 $ yen, and you can arrive at town $ 2 $ with at least $ 1 $ yen left. On the other hand, if you start with $ 3 $ yen or less, you cannot arrive at town $ 2 $ with at least $ 1 $ yen left. This input example satisfies the constraints of subtasks $ 4, 5, 6, 7 $.

Sample Explanation 4

This input example satisfies the constraints of subtasks $ 6, 7 $.

见题面 Input 部分

见题面 Output 部分