문제

미국의 의료 서비스가 비싼 이유 중 하나는 많은 병원이 최첨단의 비싼 기계를 가지고 있기 때문입니다. 기계에 드는 비용은 많은 환자에게 기계를 사용하고, 환자(또는 보험)에 높은 요금을 부과해 환수할 수밖에 없습니다. 기계가 몇 명의 환자에게만 도움이 된다고 해도, 미래의 기술 발전을 도와 가격을 절감하고 환자의 걱정을 덜어주는 등 비싼 병원 기구를 구매할 합리적 이유는 물론 많습니다. 이 문제에서는 장비를 구매하는 문제를 오로지 경제적 문제로만 바라보고, 어떤 기계가 비용보다 더 많은 수입을 불러 오는지 찾아낼 것입니다.

각각 구매 비용 p_i, 사용 비용 c_i, 최대 사용 횟수 u_i로 이루어진 기계 리스트가 주어질 것입니다. 추가로, 각 기계에 대해 환자 또는 보험에 부과할 권고 금액 r_i가 주어집니다. 이는 기계를 살 때 p_i, 기계를 사용할 때마다 ci를 지불한다는 뜻입니다; 하지만 환자가 기계를 사용할 때 당신에게 r_i를 지불합니다. 어떤 기계도 u_i번을 초과해 사용할 수 없습니다. 만약 수요가 u_i보다 높다면, 첫 u_i명의 환자에게만 기계를 사용할 수 있습니다. 환자 리스트도 주어지는데, 각 환자가 어떤 기계를 사용하고 싶어하는지 주어집니다. 이 정보를 가지고, 어떤 기계가 수익을 내는지 판단합시다.

입력

첫 줄에 데이터 셋의 수 K가 주어지고, K개의 데이터 셋이 아래의 형식으로 주어집니다:

각 데이터 셋의 첫 줄은 두 정수 n, m으로 이루어집니다. n <= 10000은 환자의 수이며, m <= 1000은 당신이 고려해야 할 기계의 수입니다. 

이후 m개의 줄 각각에 한 기계에 대한 설명을 담은 네 정수 p_i, c_i, u_i, r_i가 주어집니다. 마지막으로 n개의 줄 각각에 j번째 방문에 사용해야 하는 기계의 번호를 나타내는 하나의 정수 m_j가 1 <= m_j <= m을 만족하며 들어옵니다.

출력

각 데이터 셋에 대해, 별개의 줄에 x가 데이터 셋의 번호를 나타내는 "Data Set x:"를 출력합니다. 이후, 구매하는 것이 수익성이 있는 모든 기계를 출력합니다. (총 수입이 총 지출 초과라는 뜻입니다.) 숫자는 한 줄에 하나, 정렬된 순서로 출력합니다. 각 데이터 셋 끝에는 공백 한 줄이 있습니다.