화성의 왕

화성에 작은 왕국이 있다. 왕국에는 도시가 여러 개 있고 그중 일부는 지방 거점이다. 수도는 지방 거점일 수도 있고 아닐 수도 있다. 도시는 일방통행 도로로 이어져 있으며 도로는 빨간색 아니면 파란색이다. 한 도시에서 나가는 도로는 색깔마다 최대 한 개다.

왕은 해마다 여행을 떠난다. 여행은 수도에서 출발해 도로 $L$개를 지나고 반드시 지방 거점에서 끝난다. 지나간 도로의 색을 순서대로 연대기에 적는데, 빨간 도로는 0, 파란 도로는 1로 적는다. 그래서 한 해의 기록은 길이 $L$인 이진 문자열이다.

아레스 왕은 규칙을 하나 지켰다. 해마다 새 경로를 고르되 그 기록이 전년도 기록보다 커야 한다. 기록은 앞자리 0을 허용하는 이진수로 보고 크기를 비교한다. 즉위 첫해에는 아무 경로나 골라도 된다. 더 고를 경로가 없으면 왕은 재위를 마쳐야 한다. 아레스는 재위 기간이 가장 길어지도록 경로를 골랐다.

바샤는 연대기의 일부만 가지고 있어서 다음 질문에 스스로 답하지 못한다.

• 재위 $K$년째에 왕이 고른 경로는 무엇인가? 재위 연도는 1부터 센다.
• 기록이 $S$인 경로를 왕이 고른 해는 재위 몇 년째인가?
• 기록이 $S$인 경로 바로 다음에 왕이 고른 경로는 무엇인가?
• 기록이 $S$인 경로 바로 앞에 왕이 고른 경로는 무엇인가?

바샤 대신 이 질문에 답하는 프로그램을 작성하시오.

첫째 줄에 정수 다섯 개 $N$, $M$, $F$, $L$, $Q$가 주어진다. 차례대로 도시 수, 도로 수, 지방 거점 수, 한 해 여행에서 지나는 도로 수, 질문 수다. ($1 \le N \le 50$, $1 \le M \le 100$, $1 \le F \le N$, $1 \le L \le 60$, $1 \le Q \le 10000$)

도시 번호는 1번부터 $N$번까지이고 수도는 1번이다.

다음 $M$개 줄에는 도로가 하나씩 주어진다. 각 줄에 정수 세 개 $A_i$, $B_i$, $C_i$가 있고, $i$번 도로가 도시 $A_i$에서 도시 $B_i$로 가는 일방통행 도로이며 색은 $C_i$라는 뜻이다. 빨간색이면 0, 파란색이면 1이다.

다음 줄에는 서로 다른 정수 $F$개가 주어진다. 지방 거점인 도시의 번호다.

마지막 $Q$개 줄에는 질문이 하나씩 주어진다. 형식은 다음 넷 중 하나다.

• ? K: 재위 $K$년째에 왕이 고른 경로는 무엇인가? ($1 \le K \le 5 \times 10^{18}$)
• ! S: 기록이 $S$인 경로를 왕이 고른 해는 재위 몇 년째인가?
• > S: 기록이 $S$인 경로 바로 다음에 왕이 고른 경로는 무엇인가?
• < S: 기록이 $S$인 경로 바로 앞에 왕이 고른 경로는 무엇인가?

$S$는 0과 1로 이루어진 길이 $L$인 문자열이고, 왕이 실제로 고른 적이 있는 경로의 기록이다. 모든 질문은 올바르며 답은 항상 존재한다.

질문마다 한 줄씩 모두 $Q$개 줄을 출력한다. ! 질문에는 십진수 정수 하나를 출력한다. 나머지 질문에는 답이 되는 경로의 기록, 곧 0과 1로 이루어진 길이 $L$인 문자열을 출력한다.