+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- Hezardastan, a leading information technology development group in Iran, has launched a new project: a private space telescope with a monetized service for taking photos from all known astronomical objects (stars, planets, galaxies, constellations, ...). For special research, we need to use this service. The research must be done in $k$ consecutive days, numbered $1$ through $k$. Let $S_i$ denote the set of astronomical objects whose photo should be taken on the $i-th$ day ($1 \leq i \leq k$). We have to specify the set $S_i$ separately for each day on the photography website.  In order to specify a set of astronomical objects, we should enter the name of its members. The name of each astronomical object is a non-empty string of at most $10$ characters. The characters can be the hyphen (`-`), digits (`0` to `9`), or capital letters (`A` to `Z`). The website provides limited support of wildcards for entering a set of astronomical object names. More specifically, each entered string on the website can refer to multiple astronomical objects by having at most one asterisk (`*`), either in its beginning or its end (but not both). The asterisk matches any string (including the empty string). For example, `A*` refers to all known objects whose name starts with `A`, while `*99` refers to all objects whose name ends with `99` (including the name `99` itself if there is an astronomical object with this name). We have to pay $1000$ dollars for each photo. In order to reduce the load on the service website, Hezardastan has put an additional tax on the data entry: we have to pay $1$ extra dollar for each string entered to specify a set of astronomical objects. So for example, we have to pay $5002$ dollars by entering the set `A*`, `*B` if there are $5$ astronomical objects whose name starts with `A` or ends with `B`. Given the name of all the known astronomical objects and the sets $S_1, \dots, S_k$, your task is to find a minimum cost representation for each $S_i$. # ورودی The input starts with a line containing two space-separated integers $n$ ($1 \leq n \leq 1000$) and $k$ ($1 \leq k \leq 100$). The second line contains $n$ space-separated unique strings, as the names of all known astronomical objects. The objects are numbered $1$ through n in the same order. The next $k$ lines specify $S_1$,...,$S_k$, one set per line. Each line starts with $S_i$ (size of $S_i$) followed by $S_i$ integers, the numbers of the objects in $S_i$. # خروجی Print a single line for each day in the output. The $i-th$ line must start with the minimum possible cost to take the photos of the $i-th$ day. It should then contain a representation of $S_i$ for such a minimum cost method. If the representation contains $m$ elements, print the integer $m$, followed by the m elements. All the numbers and strings in the line should be separated by single space characters. If there are multiple optimum representations for a set, you can print any one of them. ## ورودی نمونه ۱ ``` 8 7 K-PAX SIRIUS REGULUS ARCTURUS BELLATRIX ANDROMEDA CYGNUS SCORPIUS 8 1 2 3 4 5 6 8 7 6 2 3 4 7 8 6 5 1 2 3 5 8 3 5 6 7 2 2 8 0 1 1 ```` ## خروجی نمونه ۱ ``` 8001 1 * 6002 2 A* *S 5003 3 *X R* S* 3003 3 AN* B* C* 2001 1 S* 0 0 1001 1 K* ````

حل سؤال در بانک سؤالات