This is a communication problem.

The territory of country P can be viewed as a directed graph with $N$ vertices and $M$ edges. The $i$-th edge ($0 \leq i \leq M-1$) starts at $U_i$, ends at $V_i$, and has a length of $W_i$. The vertices are numbered with positive integers from $0$ to $N-1$.

In [PER #2] Intelligence Transmission, you (the Participant) successfully obtained the location of the "Public Easy Round #2" competition through the guidance of a mole. To prevent a similar situation from happening again, country P has ordered that the next competition process will be divided into $Q$ days. For each $0 \leq i \leq Q-1$, the $i$-th exam requires all candidates to arrive at vertex $S_i$ before they can proceed to the exam location $T_i$.

You have already learned the map of country P and the $S_0, S_1, \dots, S_{Q-1}$ and $T_0, T_1, \dots, T_{Q-1}$ for the upcoming $Q$ exams. You wish to calculate the shortest path from vertex $S_i$ to vertex $T_i$ for each $0 \leq i \leq Q-1$ to plan your travel routes for the exams.

Unfortunately, due to a communication transmission failure, the lengths of exactly $K$ edges $E_0, E_1, \dots, E_{K-1}$ were lost. Fortunately, you discovered that all these edges with missing lengths share the same starting vertex, i.e., the values of $U_{E_0}, U_{E_1}, U_{E_2}, \dots, U_{E_{K-1}}$ are all equal.

Using your portable communication device, you sent the indices of the edges with missing lengths, $E_0, E_1, \dots, E_{K-1}$, to the mole, Spy. Subsequently, the mole, Spy, can send you a 0/1 string of length at most $1\,000$. You need to use this information to find the shortest path from $S_i$ to $T_i$ for each $i$.

Implementation Details

This is a communication problem; only C++ is supported.

You need to submit two programs: the program Spy describes the strategy for the mole to send information to you, and the program Participant describes your strategy.

Spy

You must include the header Spy.h and implement the following function:

std::string SpySolve(int N, int M, int Q, int K, std::vector <int> U, std::vector <int> V, std::vector <long long> W, 
                            std::vector <int> S, std::vector <int> T, std::vector <int> E);

• This function will be called exactly once per test case.
• The parameter N represents the number of vertices $N$.
• The parameter M represents the number of directed edges $M$.
• The parameter Q represents the number of days of the competition $Q$.
• The parameter K represents the number of edges with missing lengths $K$.
• U is an array of length $M$ ($U_0, U_1, \dots, U_{M-1}$) describing the starting vertex of each edge.
• V is an array of length $M$ ($V_0, V_1, \dots, V_{M-1}$) describing the ending vertex of each edge.
• W is an array of length $M$ ($W_0, W_1, \dots, W_{M-1}$) describing the length of each edge.
• S is an array of length $Q$ ($S_0, S_1, \dots, S_{Q-1}$) describing the starting vertex of each query.
• T is an array of length $Q$ ($T_0, T_1, \dots, T_{Q-1}$) describing the ending vertex of each query.
• E is an array of length $K$ ($E_0, E_1, \dots, E_{K-1}$) describing the indices of the missing edges.
• You need to return a string $Z$ consisting only of 0 and 1, describing the information Spy sends to the Participant.

Participant

You must include the header Participant.h and implement the following function:

void ParticipantSolve(int N, int M, int Q, int K, std::vector <int> U, std::vector <int> V, std::vector <long long> W, 
                            std::vector <int> S, std::vector <int> T, std::vector <int> E, std::string Z);

• This function will be called exactly once per test case.
• The parameters N, M, Q, K, U, V, W, S, T, E are the same as in SpySolve.
• Specifically, for all $0 \leq i \leq K-1$, $W_{E_i} = -1$, indicating that the length information for these edges is lost.
• Z is the 0/1 string sent by Spy to the Participant.

You must call the following function exactly $Q$ times:

void Report(std::vector<int> P);

• You must call this function exactly $Q$ times per test case.
• For the $i$-th call ($0 \leq i < Q$), the parameter P must describe the shortest path for the $i$-th query.
• Let the length of P be $L$. You must ensure that $A_{P_0} = S_i$, $B_{P_{L-1}} = T_i$, and for any $0 \leq k \leq L-2$, $B_{P_k} = A_{P_{k+1}}$.
• In other words, P describes the indices of the edges on the path in order.
• You may submit any valid shortest path.

Examples

Input 1

5 5 3 1
0 1 2
0 2 3
0 3 1
1 4 5
2 4 5
0 4 
1 4 
0 3 
1

Output 1

2 0 3
1 3
1 2

Note

The directed graph in this dataset is shown below:

For the first query, the optimal path is $0 \stackrel{e_0}{\longrightarrow} 1 \stackrel{e_3}{\longrightarrow} 4$, with a path length of $7$.

For the second query, the optimal path is $1 \stackrel{e_3}{\longrightarrow} 4$, with a path length of $5$.

For the third query, the optimal path is $0 \stackrel{e_2}{\longrightarrow} 3$, with a path length of $1$.

Therefore, the Participant program should call the functions in the following order:

• Report({ 0, 3 });
• Report({ 3 });
• Report({ 2 });

Input 2

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

Output 2

2 0 3
2 0 4
3 6 5 3
1 5

Subtasks

For $100\%$ of the data, $2 \leq N \leq 300$, $1 \leq M \leq N \times (N-1)$, $1 \leq Q \leq 60$, $1 \leq K \leq 5$, $0 \leq U_i, V_i, S_i, T_i \leq N - 1$, $1 \leq W_i \leq 10^{16}$, $0 \leq E_i \leq M-1$.

For $100\%$ of the data, there are no multiple edges or self-loops in the graph (i.e., $(A_i, B_i)$ are distinct, and $A_i \neq B_i$), there are no duplicate queries (i.e., $(S_i, T_i)$ are distinct), the start and end points of each query are different ($S_i \neq T_i$), and $E_0, E_1, \dots, E_{K-1}$ are distinct.

For $100\%$ of the data, it is guaranteed that there is at least one valid path from $S_i$ to $T_i$, and $U_{E_0} = U_{E_1} = U_{E_2} = \dots = U_{E_{K-1}}$.

Let $Y$ be the maximum length of the 0/1 string that Spy can return, and $L$ be the length of the 0/1 string you return.

• Property A: It is guaranteed that there exists a shortest path from $S_i$ to $T_i$ such that the number of edges traversed does not exceed $10$.

For subtask 2, your score depends on the value of $L$: