길을 잃었을까? (라지)

무료 셔틀 회사가 도시를 잇는 일방통행 노선 $M$개를 운행한다. 각 노선이 어느 도시에서 출발해 어느 도시로 가는지는 알지만 길이는 정확히 모른다. $i$번 노선의 길이는 $a_i$ 이상 $b_i$ 이하의 정수 하나로 정해져 있다.

나는 1번 도시에서 2번 도시로 가려고 탈 노선을 순서대로 적어 두었다. 내 길찾기 실력이 미덥지 않으니 이 경로를 검사해 달라.

경로의 노선을 앞에서부터 하나씩 본다. 앞의 노선은 모두 내가 적은 대로 탔다고 하자. 모든 노선의 길이를 각자의 범위 안에서 정하고 지금 노선의 도착 도시에서 2번 도시까지 이어 갈 방법을 골라서, 내가 지금까지 탄 구간을 1번 도시에서 2번 도시로 가는 최단 경로의 앞부분으로 만들 수 있으면 이 노선은 괜찮다. 괜찮지 않은 첫 노선의 번호를 구하라.

예를 들어 노선이 다음 다섯 개라고 하자.

내가 적은 경로가 마운틴뷰, 파리, 모스크바, 런던, 즉 2번, 4번, 5번 노선이라고 하자. 2번 노선은 괜찮다. 2번 노선이 500이고 3번 노선이 400이면 마운틴뷰에서 파리를 거쳐 런던까지가 900인데 마운틴뷰에서 런던으로 바로 가는 노선은 길어야 1000이므로, 최단 경로가 2번 노선으로 시작한다. 4번 노선은 괜찮지 않다. 파리를 지난 뒤에도 런던까지 가야 하는데 마운틴뷰, 파리, 모스크바, 런던은 짧아야 1001이고 1번 노선은 길어야 1000이기 때문이다. 그래서 답은 4번이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 양의 정수 $N$, $M$, $P$가 주어진다. $N$은 도시의 수이고 도시에는 1번부터 $N$번까지 번호가 붙는다. $M$은 노선의 수이고, $P$는 내가 적어 둔 경로에 들어 있는 노선의 수다.

다음 $M$개 줄에는 각각 정수 $u_i$, $v_i$, $a_i$, $b_i$가 주어진다. $u_i$번 도시에서 $v_i$번 도시로 가는 일방통행 노선이 있고 그 길이는 $a_i$ 이상 $b_i$ 이하의 정수다. 노선에는 입력에 나온 순서대로 1번부터 $M$번까지 번호가 붙는다.

마지막 줄에는 1 이상 $M$ 이하의 서로 다른 정수 $P$개가 주어진다. 내가 타는 노선의 번호를 순서대로 나열한 것이다.

제한

• $1 \le T \le 10$
• $2 \le N \le 1000$
• $1 \le M \le 2000$
• $1 \le P \le 500$
• $1 \le u_i, v_i \le N$
• $1 \le a_i \le b_i \le 1000000$
• 내가 적어 둔 경로는 1번 도시에서 시작해 2번 도시에서 끝나는 올바른 경로다.
• 같은 두 도시를 잇는 노선이 여러 개일 수 있고, 출발 도시와 도착 도시가 같은 노선도 있을 수 있다. 내 경로는 같은 도시를 여러 번 지날 수 있지만 같은 노선을 두 번 타지는 않는다.

각 테스트 케이스마다 한 줄에 "Case #x: n"을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, n은 1번 도시에서 2번 도시로 가는 최단 경로에 결코 들어갈 수 없는 첫 노선의 번호다. 그런 노선이 없으면 n 자리에 "Looks Good To Me"를 출력한다.