Освещение сцены

Для освещения сцены были установлены n прожекторов. Прожекторы стоят вдоль сцены и пронумерованы слева направо числами от 1 до n. Прожектор с номером i имеет мощность p**i.

Сцена будет считаться освещенной, если суммарная мощность включенных прожекторов не меньше Z. Ситуация осложняется тем, что каждый из работающих прожекторов должен быть подключен к определенному набору разъемов. Всего имеется k различных разъемов, i-й прожектор имеет ki выходов и должен быть подключен к разъемам a**i,1, a**i,2, ..., a**i,k**i. В каждый момент времени к разъему может быть подключено не более одного прожектора.

Место установки источника питания еще не определено. Чтобы оптимизировать процесс прокладки проводов, перед вами поставили следующую задачу: для каждого i от 1 до n найдите минимальное r**i, что среди прожекторов с номерами от i до r**i включительно можно выбрать подмножество одновременно работающих прожекторов так, что сцена будет освещена.

Первая строка содержит три целых числа n, k и Z (1 ≤ n ≤ 105, 1 ≤ k ≤ 8, 1 ≤ Z ≤ 109). Вторая строка содержит n целых чисел p1, ..., p**n (1 ≤ p**i ≤ 109). Следующие n строк содержат описание разъемов, к которым нужно подключать прожекторы, i-я из них содержит число k**i (1 ≤ ki ≤ k), а также k**i различных чисел a**i,1, a**i,2, ..., a**i,k**i (1 ≤ a**i,j ≤ k).

Выведите n строк: в i строке выведите число r**i, если такое существует, и −1 иначе.