장비 구매

의료비가 비싼 이유 중 하나는 많은 병원이 매우 첨단이면서 값비싼 장비를 갖추고 있기 때문이다. 이러한 장비의 구매 비용은 어떻게든 회수해야 하며, 보통 많은 환자에게 장비를 사용하고 그 사용료를 환자(또는 보험사)에게 청구하는 방식으로 회수한다. 값비싼 장비를 구매하는 데에는 여러 정당한 이유가 있지만, 여기서는 구매를 순전히 경제적인 관점에서만 판단한다. 즉, 어떤 장비가 그 비용보다 더 많은 돈을 벌어들이는지를 알아낸다.

장비 목록이 주어진다. 장비 $i$는 구매 비용 $p_i$, 사용 비용 $c_i$, 최대 사용 횟수 $u_i$, 그리고 환자(또는 보험사)가 한 번 사용할 때마다 지불하는 청구 금액 $r_i$를 가진다. 장비를 사려면 $p_i$를 한 번 지불하고, 사용할 때마다 $c_i$를 지불하며, 환자는 사용할 때마다 당신에게 $r_i$를 지불한다. 한 장비는 최대 $u_i$번까지만 사용할 수 있다. 수요가 $u_i$보다 크면 처음 $u_i$명의 환자만 진료할 수 있다.

또한 환자 방문 목록이 주어지며, 각 방문은 필요한 장비 하나를 지정한다. 장비 $i$를 필요로 하는 방문의 수를 $d_i$라고 하면, 장비 $i$는 실제로 $s_i = \min(d_i, u_i)$번 사용되어 $s_i \cdot r_i$의 수입을 얻고, 총 지출은 $p_i + s_i \cdot c_i$가 된다. 수입이 지출보다 엄격히 클 때 그 장비는 이득이 된다. 이득이 되는 장비가 무엇인지 구하라.

첫째 줄에 데이터 집합의 개수 $K$가 주어진다. 이어서 $K$개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫째 줄에는 두 정수 $n$과 $m$이 주어진다. $n \le 10000$은 환자 방문의 수이고, $m \le 1000$은 검토 중인 장비의 수이다.

다음 $m$개의 줄에는 각각 한 장비를 설명하는 네 정수 $p_i$, $c_i$, $u_i$, $r_i$가 주어진다.

그 다음 $n$개의 줄에는 각각 하나의 정수 $m_j$ ($1 \le m_j \le m$)가 주어지며, 이는 $j$번째 방문이 필요로 하는 장비의 번호이다.

각 데이터 집합에 대해 먼저 Data Set x: 형식의 줄을 출력한다. 여기서 $x$는 데이터 집합의 번호이며 1부터 시작한다. 그다음 이득이 되는 모든 장비의 번호를 오름차순으로 한 줄에 하나씩 출력한다. 연속한 데이터 집합 사이는 빈 줄로 구분한다.