Anna and Bruno are taking a Kanji test at school. They know $N$ Kanji characters, labeled from $0$ to $N-1$, and $M$ words, labeled from $0$ to $M-1$. Each word consists of Kanji characters they know; the first character of word $i$ is $A_i$ and the last character is $B_i$. For all words, $A_i \neq B_i$. Furthermore, all pairs $(A_i, B_i)$ are distinct; that is, if $i \neq j$, then $(A_i, B_i) \neq (A_j, B_j)$. Each word also has a required time $C_i$ to write it.

The test consists of $Q$ problems of the following type: Problem $j$: Provide one "Kanji Shiritori" that starts with Kanji $S_j$ and ends with Kanji $T_j$.

For all problems, $S_j \neq T_j$. Furthermore, all pairs $(S_j, T_j)$ are distinct; that is, if $i \neq j$, then $(S_i, T_i) \neq (S_j, T_j)$.

A "Kanji Shiritori" is a sequence of words such that the last character of each word is the same as the first character of the next word, as shown in Figure 1. A Kanji Shiritori starting with Kanji $S_j$ and ending with Kanji $T_j$ is a Kanji Shiritori where the first character of the first word is $S_j$ and the last character of the last word is $T_j$.

Figure 1: Example of a Kanji Shiritori starting with Kanji $S_j = \text{「報」}$ and ending with Kanji $T_j = \text{「情」}$

There may be several possible Kanji Shiritori that satisfy the conditions. Since the test time is short, you must provide one with the minimum total required time (if there are multiple, any one of them is acceptable). The required time for a Kanji Shiritori is the sum of the required times of all words included in it.

Just before the test, Bruno forgot the required times $C_{U_0}, C_{U_1}, \dots, C_{U_{K-1}}$ for $K$ words. Coincidentally, these $K$ words all share the same first character. Anna was informed of this by Bruno, but since there was no time before the test started, she decided to convey the information to Bruno during the test. During the test, Anna can send $0$ or $1$ to Bruno by tapping on the desk. Anna wants to minimize the number of times she sends $0$ or $1$. Can Bruno get a perfect score on the test?

Implementation Details

You must submit two files in the same programming language. The first file is named Anna.c or Anna.cpp. This file implements Anna's strategy and must implement the following routine:

• void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[])

This routine is called exactly once at the beginning. Argument $N$ is the number of Kanji characters. Argument $M$ is the number of words. Argument $A$ is an array of length $M$, where $A[i]$ is the index of the first character of word $i$. Argument $B$ is an array of length $M$, where $B[i]$ is the index of the last character of word $i$. Argument $C$ is an array of length $M$, where $C[i]$ is the required time to write word $i$. Argument $Q$ is the number of problems. Argument $S$ is an array of length $Q$, where $S[j]$ is the index of the first character of the answer to problem $j$. Argument $T$ is an array of length $Q$, where $T[j]$ is the index of the last character of the answer to problem $j$. Argument $K$ is the number of words for which Bruno forgot the required time. Argument $U$ is an array of length $K$, where $U[0], U[1], \dots, U[K-1]$ are the indices of the words for which Bruno forgot the required time.

In the program, you can call the following routine to send $0$ or $1$ to Bruno:

• void Tap(int x)

The argument $x$ is the $0$ or $1$ to be sent to Bruno. $x$ must be $0$ or $1$. If this is not satisfied, it results in Wrong Answer [1]. If the number of calls to Tap exceeds $1000$, it results in Wrong Answer [2].

If a call to Tap is judged as incorrect, the program execution is terminated at that point.

The second file is named Bruno.c or Bruno.cpp. This file implements Bruno's strategy and must implement the following routine:

• void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[])

This routine is called exactly once after Anna has been called. Arguments $N, M, A, B, Q, S, T, K, U$ are the same as for Anna. Argument $C$ is an array of length $N$, where $C[i]$ is the required time to write word $i$. However, if $i$ is one of $U_0, U_1, \dots, U_{K-1}$, it is $-1$. Argument $L$ is the number of $0$s or $1$s sent from Anna. Argument $X$ is an array of length $L$, representing the $0$s or $1$s sent from Anna in the order $X[0], X[1], \dots, X[L-1]$.

In the program, you can call the following routine:

• void Answer(int w)

• Argument $w$ must be an integer between $0$ and $M-1$ inclusive, or $-1$. If this is not satisfied, it results in Wrong Answer [3].

• If this routine is called after $Q$ calls with $w = -1$ have already been made, it results in Wrong Answer [4].

If a call to Answer is judged as incorrect, the program execution is terminated at that point.

The program must use this routine to repeat the operation of answering one problem $Q$ times. In the $(j+1)$-th operation ($0 \le j \le Q-1$), perform the following: 1. For the sequence of words that is the answer to problem $j$, call Answer(w) with the word index as the argument, in order from the first word to the last word. 2. Then, call Answer(-1).

After Bruno is called, the answer is judged: If the number of calls with $w = -1$ is less than $Q$, it results in Wrong Answer [5]. If the length of the answer sequence for a problem is $0$, it results in Wrong Answer [6]. If in an answer for a problem, the last character of a word and the first character of the next word are different, it results in Wrong Answer [7]. If in an answer for problem $j$, the first character of the first word is not $S_j$ or the last character of the last word is not $T_j$, it results in Wrong Answer [8]. * If for any problem, the required time of the answer is not the minimum, it results in Wrong Answer [9].

Examples

Input 1

4 5 3 2
2 1 10
0 2 20
3 1 30
0 1 40
3 0 50
3 0 50
3 1 30
0 1 30
1
3

Output 1

Accepted : L = 4

Note

The example input above corresponds to the following parameters: $N=4, M=5, Q=3, K=2$. Words: 0: $2 \to 1$, $C=10$ 1: $0 \to 2$, $C=20$ 2: $3 \to 1$, $C=30$ 3: $0 \to 1$, $C=40$ 4: $3 \to 0$, $C=50$ Problems: 0: $3 \to 0$, $Z=50$ 1: $3 \to 1$, $Z=30$ 2: $0 \to 1$, $Z=30$ Forgotten words: $U=\{1, 3\}$.

Constraints

All input data satisfy the following conditions: $2 \le N \le 300$. $1 \le M \le N \times (N - 1)$. $0 \le A_i < N$ ($0 \le i < M$). $0 \le B_i < N$ ($0 \le i < M$). $A_i \neq B_i$ ($0 \le i < M$). $(A_i, B_i) \neq (A_j, B_j)$ ($0 \le i < j < M$). $1 \le C_i \le 10^{16}$ ($< 2^{54}$) ($0 \le i < M$). $1 \le Q \le 60$. $0 \le S_j < N$ ($0 \le j < Q$). $0 \le T_j < N$ ($0 \le j < Q$). $S_j \neq T_j$ ($0 \le j < Q$). $(S_i, T_i) \neq (S_j, T_j)$ ($0 \le i < j < Q$). A Kanji Shiritori starting with Kanji $S_j$ and ending with Kanji $T_j$ exists ($0 \le j < Q$). $1 \le K \le 5$. $0 \le U_k < M$ ($0 \le k < K$). $U_i \neq U_j$ ($0 \le i < j < K$). * The first characters of the words Bruno forgot are the same. That is, $A_{U_0} = A_{U_1} = \dots = A_{U_{K-1}}$.

Subtasks

Subtask 1 [10 points]

• $Q \le 10$.
• For each problem, there exists an answer that uses 10 or fewer words.
• Anna can call Tap up to 1000 times.

Subtask 2 [22 points]

• Anna can call Tap up to 180 times.

Subtask 3 [8 points]

• Anna can call Tap up to 160 times.

Subtask 4 [40 points]

• Anna can call Tap up to 90 times.

Subtask 5 [20 points]

• Let $L$ be the maximum number of Tap calls across all test cases in this subtask. The score for this subtask is:
  • If $L \le 64$, 20 points.
  • If $64 < L < 90$, $\lfloor (\frac{90 - L}{90 - 64})^2 \times 20 \rfloor$ points (where $\lfloor x \rfloor$ denotes the largest integer not exceeding $x$).
  • If $L \ge 90$, 0 points.