Creating Fake News

A social network has $n$ people, numbered 1 to $n$. One news story is described by $d$ real numbers $c_1, c_2, \dots, c_d$, where $c_j$ says how hard the story pushes topic $j$. These numbers do not have to be integers.

Person $i$ comes with an interest vector $a_{i1}, a_{i2}, \dots, a_{id}$ and a threshold $t_i$. Person $i$ likes a story exactly when $a_{i1}c_1 + a_{i2}c_2 + \dots + a_{id}c_d = t_i$. A sum above the threshold is no better than a sum below it, so only an exact match works.

Someone who receives the story and likes it passes it on to everyone on their share list. Someone who does not like it passes it to nobody. You pick the people who receive the story first, and you may pick several, but every one of them gets the same single story.

Design one story that all $n$ people like. Such a story does not always exist, and you report that when it happens. When it does exist, report the smallest number of people you have to start the story at so that every person receives it.

The first line holds the number of data sets $K$. After it come $K$ data sets.

The first line of a data set holds the number of people $n$ and the number of topics $d$. Each of the next $n$ lines describes one person: line $i$ holds the integers $a_{i1}, \dots, a_{id}$, then the threshold $t_i$, then the size $k_i$ of the share list, then the $k_i$ numbers of the people person $i$ sends news to.

$1 \le K \le 20$, $1 \le n \le 100$, $1 \le d \le 20$, $|a_{ij}| \le 100$, $|t_i| \le 1000$, and $0 \le k_i \le n - 1$. The numbers on a share list are distinct and never include $i$.

For each data set, print Data Set x: on a line by itself, where $x$ is the number of the data set counting from 1. On the next line print the smallest number of people you have to start the story at so that everyone receives it, or Impossible when no story satisfies all $n$ people. Print a blank line after each data set.