곱해진 수들

Eugênio는 수를 곱하는 것을 즐기는 뛰어난 수학자이다.

어느 날 그는 1부터 M까지 번호가 붙은 M개의 종이 조각을 발견했고, 각 조각에는 꼭짓점 하나가 그려져 있었다. 이 꼭짓점을 M-꼭짓점이라 하자. 각 꼭짓점에는 서로 다른 소수가 표시되어 있었다. 또한 소수들은 정렬되어 있었다. i번째 종이 조각에 있는 꼭짓점의 표시를 pi라 하면, i < j인 모든 쌍에 대해 pi < pj이다.

종이 조각을 발견한 뒤 Eugênio는 N개의 다른 꼭짓점을 그리기로 했고, 이를 N-꼭짓점이라 하자. 그리고 M-꼭짓점과 N-꼭짓점 사이에 간선을 추가했다. 그는 M-꼭짓점과 M-꼭짓점을 잇지 않았고 N-꼭짓점과 N-꼭짓점도 잇지 않았지만, 두 꼭짓점 사이에 그리는 간선의 수에는 신경 쓰지 않았다. 이렇게 해서 그는 이분 멀티그래프를 얻었다.

Eugênio의 주된 관심사는 수를 곱하는 것이므로, 그는 각 N-꼭짓점에 연결된 모든 M-꼭짓점의 곱으로 표시를 하기로 했다. 어떤 M-꼭짓점이 여러 간선으로 N-꼭짓점에 연결되어 있으면, 그 표시는 N-꼭짓점의 표시를 만드는 과정에서 여러 번(연결하는 간선의 수만큼) 곱해진다.

각 N-꼭짓점 i는 결국 수 ci로 표시되었다. 형식적으로 ci에 대해 다음 식을 쓸 수 있다. [c_i = \prod_{(j,i) \in E}{p_j}\text{,}] 여기서 E는 간선의 중복집합이다(E의 각 원소는 1 ≤ m ≤ M, 1 ≤ n ≤ N인 쌍 (m, n)이다). N-꼭짓점의 표시를 만든 뒤 Eugênio는 간식을 사러 갔고, 간식은 토로와 커피였다. 토로를 먹던 중 Eugênio는 실수로 커피를 쏟아서 M-꼭짓점의 표시 p1, . . . , pM을 읽을 수 없게 되었다.

커피 때문에 사라진 정렬된 소수들을 되찾도록 도와줄 수 있는가?

첫째 줄에는 세 정수 M, N, K가 주어진다. 각각 M-꼭짓점의 수, N-꼭짓점의 수, 서로 다른 간선의 수이다. 이 값은 1 ≤ M, N < 103, 1 ≤ K < 104을 만족한다.

다음 줄에는 N개의 수 ci가 주어진다. 이는 N-꼭짓점의 표시이다. 이 값은 1 < ci < 1015을 만족한다.

마지막으로 K개의 줄이 주어지고, 각 줄에는 세 수 m, n, d가 있다. 이는 M-꼭짓점 m과 N-꼭짓점 n 사이에 d개의 간선이 있음을 나타낸다. 이 수는 1 ≤ m ≤ M, 1 ≤ n ≤ N, 1 ≤ d ≤ 50을 만족한다.

모든 꼭짓점(M-꼭짓점과 N-꼭짓점 모두)의 차수가 적어도 1임이 보장된다. 다시 말해, 모든 꼭짓점에는 연결된 간선이 적어도 하나 있다.

Eugênio를 잠 못 이루게 한 M-꼭짓점의 표시, 즉 인덱스 1, . . . , M에 해당하는 정렬된 소수 M개를 한 줄에 출력한다.