Бұл жылы ICPC World Finals-тің бас демеушісі Freedom Holding corp.!

| | | | | | |:-------------------------------------|:---------------------------------------------------------------|-------------------------------------:|-------------------------------------------------------------:|-------------------------------------:| |        |
|        |
|        |

Қазақстанда өтетін финал қарсаңында ұйымдастырушылар іс-шара өтетін қаланы құпия сақтап, бірінші кезекте сол қала туралы кейбір фактілерді хабарлауды шешті.

Кейбір фактілер бар: қала «өзен бойында», «таулардың жанында», «батпақты жерде», «теңіз жағасында» немесе «халқы миллионнан кем емес», «әуежайы бар», «ЧРК финалистері осы қаладан бар».

Сонымен қатар, финалды өткізуге мүмкін болатын \(n\) қала бар, олар \(1\)-ден \(n\)-ге дейін нөмірленген. Әрбір қала үшін әрбір фактінің осы қалаға қатысты дұрыс (шындық) немесе бұрыс (жалған) екендігі белгілі.

Ұйымдастырушылар бірнеше қалалар жиынтығын дайындады. Енді әрбір жиынтық үшін олар сол қалалар туралы бірнеше фактілерді хабарлағысы келеді, форматта: шындық «өзен бойында» немесе жалған «теңіз жағасында». Фактілер қалалар жиынтығын әдіспен таңдап қалған қалаларды алып тастау үшін хабарлануы керек. Ұйымдастырушылар интригасын сақтау үшін мүмкіндігінше аз фактілерді хабарлауды қалайды. Мысалы, егер «теңіз жағасында» деген фактіні хабарласа, онда Алматы мен Астана қалалары шығарылады, немесе егер «өзен бойында емес» деген фактіні хабарласа, онда Астана, Атырау, Семей сияқты қалалар шығарылады, т.с.с.

Финалға дайындық қызу жүріп жатыр! Ұйымдастырушыларға әрбір қалалар жиынтығы үшін барлық қалаларды алып тастап, тек осы жиынтық қалатын минималды фактілер санын дайындауға көмектесіңіз.

Енгізу

Бірінші жолда екі сан \(n\) және \(m\) (\(1 \le n,m \le 200, \)n \cdot m \le 200~) — қалалар саны және фактілер саны.

Келесі \(n\) жолдың әрқайсысында ұзындығы \(m\) нөлдер мен бірлер жолы бар — \(i\)-ші жолдың \(j\)-ші позициясында егер \(j\)-ші факт \(i\) қаласына қатысты болса \(1\), әйтпесе \(0\) тұрады.

Келесі жолда \(q\) саны (\(1 \le q \le 10^5\)) — дайындалған қалалар жиынтығының саны. Келесі \(q\) жолда осы жиынтықтардың сипаттамасы беріледі: \(k\) және \(b_1, \ldots, b_k\) (\(1 \le k \le n, 1 \le b_i \le n\)) — жиынтықтағы қалалар саны және қалалардың нөмірлері. Барлық жиынтықтардың өлшемдерінің қосындысы \(3 \cdot 10^5\)-тан аспайтындығы кепілдендірілген.

Шығару

Әрбір жиынтық үшін осы жиынтықты хабарлау үшін қажетті минималды фактілер санын шығарыңыз.

Мысалдар

Енгізу 1

6 5
11111
00101
00001
10001
00010
01000
4
2 3 5
2 3 4
3 1 3 4
6 1 2 3 4 5 6

Жауап 1

3
2
-1
0

Ескертпелер

Мысалда 6 қала берілген, олар келесі ретпен нөмірленген: Астана, Атырау, Қостанай, Қызылорда, Талдықорған, Шымкент. Сондай-ақ, келесі фактілер бар: «Бұл қала бір уақытта Қазақстанның астанасы болған», «Қаланың халқы миллионнан көп», «Қаланың атауы А әрпінен басталады», «Тима осы қалада тұрған», «ҚРК 2024 финалында осы қаладан қатысушы бар».

Бірінші қалалар жиынтығы Қостанай және Талдықорған келесідей болжамдануы мүмкін: қала астана болмаған, халқы миллионнан көп емес, атауы А әрпінен басталмайды. Осылайша, тек берілген жиынтықтың қалалары қалады. 3 факт қолданылды. Берілген жиынтықты аз фактілермен алу мүмкін еместігін көрсетуге болады.

Екінші қалалар жиынтығы Қостанай және Қызылорда келесідей болжамдануы мүмкін: атауы А әрпінен басталмайды, ҚРК 2024 финалында осы қаладан қатысушы бар. Сондай-ақ, берілген жиынтықты аз фактілермен алу мүмкін еместігін көрсетуге болады.

Үшінші қалалар жиынтығын берілген фактілермен алу мүмкін емес.

Төртінші жиынтықта ешқандай фактілер қолданылмайды. Ешқандай қалалар шығарылмайды және бастапқы қалалар тізімі қалады.