A company of $n$ friends wants to order exactly two pizzas. It is known that in total there are $9$ pizza ingredients in nature, which are denoted by integers from $1$ to $9$.

Each of the $n$ friends has one or more favorite ingredients: the $i$-th of friends has the number of favorite ingredients equal to $f_i$ ($1 \le f_i \le 9$) and your favorite ingredients form the sequence $b_{i1}, b_{i2}, \dots, b_{if_i}$ ($1 \le b_{it} \le 9$).

The website of CodePizza restaurant has exactly $m$ ($m \ge 2$) pizzas. Each pizza is characterized by a set of $r_j$ ingredients $a_{j1}, a_{j2}, \dots, a_{jr_j}$ ($1 \le r_j \le 9$, $1 \le a_{jt} \le 9$) , which are included in it, and its price is $c_j$.

Help your friends choose exactly two pizzas in such a way as to please the maximum number of people in the company. It is known that a person is pleased with the choice if each of his/her favorite ingredients is in at least one ordered pizza. If there are several ways to choose two pizzas so as to please the maximum number of friends, then choose the one that minimizes the total price of two pizzas.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n \le 10^5, 2 \le m \le 10^5$) — the number of friends in the company and the number of pizzas, respectively.

Next, the $n$ lines contain descriptions of favorite ingredients of the friends: the $i$-th of them contains the number of favorite ingredients $f_i$ ($1 \le f_i \le 9$) and a sequence of distinct integers $b_{i1}, b_{i2}, \dots, b_{if_i}$ ($1 \le b_{it} \le 9$).

Next, the $m$ lines contain pizza descriptions: the $j$-th of them contains the integer price of the pizza $c_j$ ($1 \le c_j \le 10^9$), the number of ingredients $r_j$ ($1 \le r_j \le 9$) and the ingredients themselves as a sequence of distinct integers $a_{j1}, a_{j2}, \dots, a_{jr_j}$ ($1 \le a_{jt} \le 9$).


-----Output-----

Output two integers $j_1$ and $j_2$ ($1 \le j_1,j_2 \le m$, $j_1 \ne j_2$) denoting the indices of two pizzas in the required set. If there are several solutions, output any of them. Pizza indices can be printed in any order.


-----Examples-----
Input
3 4
2 6 7
4 2 3 9 5
3 2 3 9
100 1 7
400 3 3 2 5
100 2 9 2
500 3 2 9 5

Output
2 3

Input
4 3
1 1
1 2
1 3
1 4
10 4 1 2 3 4
20 4 1 2 3 4
30 4 1 2 3 4

Output
1 2

Input
1 5
9 9 8 7 6 5 4 3 2 1
3 4 1 2 3 4
1 4 5 6 7 8
4 4 1 3 5 7
1 4 2 4 6 8
5 4 1 9 2 8

Output
2 4

Difficulty: interview

Starter code:

Solutions:
#  author: ThePonyCoder
#  created: 23.06.2019, 21:58
#  filename: f.py
#  path: C:/Users/User/Desktop/python/Prog/CodeForces/rounds/cf_568/f.py

import os

# import random

# sys.setrecursionlimit(999999999)
import string

from math import inf
from functools import lru_cache

if os.getcwd() == 'C:\\Users\\User\\Desktop\\python\\Prog\\CodeForces' \
        or os.environ['COMPUTERNAME'] == 'USER145':
    import pdb
    
    import sys
    
    pdb = pdb.Pdb(stdin=sys.stdin, stdout=sys.stdout)
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')
    from pprint import pprint
    from hypothesis import given, settings
    from hypothesis import strategies as st


def ri():
    return [int(i) for i in input().split()]


def to_bits(l):
    ans = 0
    for i in l:
        ans |= (1 << i - 1)
    return ans


user_masks = [0 for i in range(1 << 10)]
pizzas = [[] for i in range(1 << 10)]


@lru_cache()
def count_sat_users(mask):
    ans = 0
    cmask = mask
    while cmask:
        ans += user_masks[cmask]
        cmask = (cmask - 1) & mask
    return ans


def main():
    n, m = ri()
    for _ in range(n):
        k, *a = ri()
        bits = to_bits(a)
        user_masks[bits] += 1
    
    ans = (float(-inf), float(inf), -1, -1)
    
    for i in range(m):
        c, k, *a = ri()
        bits = to_bits(a)
        pizzas[bits].append((c, i + 1, bits))  # цена, номер, маска
        pizzas[bits].sort()
        while len(pizzas[bits]) > 2:
            pizzas[bits].pop()
    # pprint(pizzas)
    
    for mask_F in range(1 << 9):
        for mask_S in range(1 << 9):
            if len(pizzas[mask_F]) and len(pizzas[mask_S]) \
                    and mask_F != mask_S:
                
                mask = mask_F | mask_S
                
                satisfied_users = count_sat_users(mask)
                
                f_pizza = next(iter(pizzas[mask_F]))
                s_pizza = next(iter(pizzas[mask_S]))
                
                summary_cost = 0
                summary_cost += f_pizza[0]
                summary_cost += s_pizza[0]
                
                ans = max(ans,
                          (satisfied_users,
                           -summary_cost,
                           s_pizza[1],
                           f_pizza[1]))
                
                # bruting all masks
                bmask = mask
                while bmask:
                    satisfied_users += user_masks[bmask]
                    bmask = (bmask - 1) & mask
            
            if len(pizzas[mask_F]) == 2:
                satisfied_users = count_sat_users(mask_F)
                
                it = iter(pizzas[mask_F])
                
                f_pizza = next(it)
                s_pizza = next(it)
                summary_cost = 0
                summary_cost += f_pizza[0] + s_pizza[0]
                ans = max(ans,
                          (satisfied_users,
                           -summary_cost,
                           s_pizza[1],
                           f_pizza[1]))
            
            if len(pizzas[mask_S]) == 2:
                satisfied_users = count_sat_users(mask_S)
                
                it = iter(pizzas[mask_S])
                
                f_pizza = next(it)
                s_pizza = next(it)
                summary_cost = 0
                summary_cost += f_pizza[0] + s_pizza[0]
                ans = max(ans,
                          (satisfied_users,
                           -summary_cost,
                           s_pizza[1],
                           f_pizza[1]))
    
    aans = [ans[2],ans[3]]
    aans.sort()
    print(*aans, sep=' ')


main()


import sys

def popcount(i):
    assert 0 <= i < 0x100000000
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24


N, M = list(map(int, sys.stdin.readline().split()))
table = [0]*(2**9)
for _ in range(N):
    S = tuple(map(int, sys.stdin.readline().split()))
    table[sum(2**(a-1) for a in S[1:])] += 1

dp = [0]*(2**9)
for s in range(2**9):
    ppc = popcount(s)
    res = table[s]
    t = s&(s-1)
    for _ in range(2**ppc - 1):
        res += table[t]
        t = (t-1)&s
    dp[s] = res                        

table = [False]*(2**9)
cost = [[] for _ in range(2**9)]
idx = [[] for _ in range(2**9)]
for i in range(M):
    T = tuple(map(int, sys.stdin.readline().split()))
    x = sum(2**(a-1) for a in T[2:])
    table[x] = True
    cost[x].append(T[0])
    idx[x].append(i+1)

minidx = [cost[x].index(min(cost[x])) if cost[x] else -1 for x in range(2**9)]
mincost = [10**10]*(2**9)
mincostidx = [(0, 0) for _ in range(2**9)]
reachable = [False]*(2**9)
for i in range(2**9):
    if not table[i]:
        continue
    for j in range(2**9):
        if not table[j]:
            continue
        reachable[i|j] = True
        if i != j:
            mi = min(cost[i])
            mj = min(cost[j])
            if mincost[i|j] > mi + mj:
                mincost[i|j] = mi + mj
                mincostidx[i|j] = (idx[i][minidx[i]], idx[j][minidx[j]])
ctr = -1
candi = []
for i in range(2**9):
    if not reachable[i]:
        continue
    if ctr > dp[i]:
        continue
    elif ctr == dp[i]:
        candi.append(i)
    else:
        ctr = dp[i]
        candi = [i]

ans = 10**11
Ans = (-1, -1)
for c in candi:
    if table[c] and len(cost[c]) > 1:
        D = cost[c][:]
        res = min(D)
        a = D.index(res)
        D.remove(res)
        r = min(D)
        b = D.index(r)
        if cost[c][b] != r:
            b += 1
        if a == b:
            b += 1
        res += r
        if ans > res:
            ans = res
            Ans = (idx[c][a], idx[c][b])
    if ans > mincost[c]:
        ans = mincost[c]
        Ans = mincostidx[c]
print(*Ans)


from sys import stdin, stdout
import itertools

n, m = list(map(int, stdin.readline().split()))

friends = [0]*512
exists = [0]*512
costs_min = [0]*512
costs_2 = [0]*512
index_min = [0]*512
index_2 = [0]*512


count_friends = [0]*512

def top_to_idx(top):
    ans = 0
    for t in top:
        ans += 1 << (t-1)
    return ans

def idx_to_top(idx):
    ans = []
    for i in range(9):
        if idx & (1 << i):
            ans.append(i+1)
    return ans

for i in range(n):
    top = list(map(int, stdin.readline().split()))[1:]
    friends[top_to_idx(top)] += 1

#print(friends)

def subset(i, j):
    for s in range(9):
        if i & (1 << s) and not (j & (1 << s)):
            return False
    return True

for i in range(512):
    for j in range(512):
        if subset(j, i):
            count_friends[i] += friends[j]

#print(count_friends)

for i in range(m):
    pizza = list(map(int, stdin.readline().split()))
    top_idx = top_to_idx(pizza[2:])
    cost = pizza[0]
    exists[top_idx] = True
    if costs_min[top_idx] == 0 or cost < costs_min[top_idx]:
        costs_2[top_idx] = costs_min[top_idx]
        index_2[top_idx] = index_min[top_idx]
        costs_min[top_idx] = cost
        index_min[top_idx] = i+1
    elif costs_2[top_idx] == 0 or cost < costs_2[top_idx]:
        costs_2[top_idx] = cost
        index_2[top_idx] = i+1

best_matches = -1
best_cost = -1
best = None
for p1 in range(512):
    for p2 in range(p1, 512):
        if not exists[p1] or not exists[p2]:
            continue
        if p1 == p2 and index_2[p1] == 0:
            continue
        p = p1 | p2
    #    print(idx_to_top(p1 | p2))
        matches = count_friends[p]
     #   print(matches)
        cost = costs_min[p1] + costs_min[p2] if p1 != p2 else costs_min[p1] + costs_2[p2]
        if best_matches == -1 or matches > best_matches or (matches == best_matches and cost < best_cost):
            best = (index_min[p1], index_min[p2]) if p1 != p2 else (index_min[p1], index_2[p2])
            best_matches = matches
            best_cost = cost

#print(best_matches)
#print(best_cost)
print(best[0], best[1])
    


import  sys
import  math
#input=sys.stdin.readline
#sys.setrecursionlimit(1000000)
I=lambda : list(map(int,input().split()))
ma =int(10000000000000000)
n,m=map(int,input().split())
a=[ma]*(515);a1=[ma]*(515);fr=[0]*(515);pos=[0]*(515)
for i in range(n):
    b=I()
    x=int(0)
    for j in range(1,b[0]+1):
        b[j]-=1
        x|=(1<<b[j])
    fr[x]+=1

min1=int(ma)
max1=int(0)
ind,ind1=int(),int()
for i in range(m):
    b=I()
    x=int(0)
    for j in range(2,b[1]+2):
        b[j]-=1
        x|=(1<<b[j])
    if a[x]!=ma:
        if fr[x]>max1:
            max1=fr[x]
            min1=a[x]+b[0]
            ind=pos[x]
            ind1=i+1
        elif fr[x]==max1:
            if b[0]+a[x]<min1:
                min1=b[0]+a[x]
                ind=pos[x]
                ind1=i+1
    if a[x]>b[0]:
        a[x]=b[0]
        pos[x]=i+1


for i in range(1,512):
    for j in range(1,512):
        if i==j or  a[i]==ma or a[j]==ma:
            continue
        k=i|j
        cnt=int(0)
        while k>0:
            cnt+=fr[k]
            k=(k-1)&(i|j)
        if cnt>max1:
            ind=pos[i]
            ind1=pos[j]
            max1=cnt
            min1=a[i]+a[j]
        if cnt==max1:
            if a[i]+a[j]<min1:
                ind=pos[i]
                ind1=pos[j]
            min1=min(min1,a[i]+a[j])

print(ind,ind1,sep=" ")

import  sys
import  math
input=sys.stdin.readline
#sys.setrecursionlimit(1000000)
I=lambda : list(map(int,input().split()))
ma =int(10000000000000000)
n,m=map(int,input().split())
a=[ma]*(515);a1=[ma]*(515);fr=[0]*(515);pos=[0]*(515)
for i in range(n):
    b=I()
    x=int(0)
    for j in range(1,b[0]+1):
        b[j]-=1
        x|=(1<<b[j])
    fr[x]+=1

min1=int(ma)
max1=int(0)
ind,ind1=int(),int()
for i in range(m):
    b=I()
    x=int(0)
    for j in range(2,b[1]+2):
        b[j]-=1
        x|=(1<<b[j])
    if a[x]!=ma:
        if fr[x]>max1:
            max1=fr[x]
            min1=a[x]+b[0]
            ind=pos[x]
            ind1=i+1
        elif fr[x]==max1:
            if b[0]+a[x]<min1:
                min1=b[0]+a[x]
                ind=pos[x]
                ind1=i+1
    if a[x]>b[0]:
        a[x]=b[0]
        pos[x]=i+1


for i in range(1,512):
    for j in range(1,512):
        if i==j or  a[i]==ma or a[j]==ma:
            continue
        k=i|j
        cnt=int(0)
        while k>0:
            cnt+=fr[k]
            k=(k-1)&(i|j)
        if cnt>max1:
            ind=pos[i]
            ind1=pos[j]
            max1=cnt
            min1=a[i]+a[j]
        if cnt==max1:
            if a[i]+a[j]<min1:
                ind=pos[i]
                ind1=pos[j]
            min1=min(min1,a[i]+a[j])

print(ind,ind1,sep=" ")

import  sys
import  math
input=sys.stdin.readline
#sys.setrecursionlimit(1000000)
#I=lambda : list(map(int,input().split()))
ma =int(10000000000000000)
n,m=map(int,input().split())
a=[ma]*(515);a1=[ma]*(515);fr=[0]*(515);pos=[0]*(515)
for i in range(n):
    b=list(map(int,input().split()))
    x=int(0)
    for j in range(1,b[0]+1):
        b[j]-=1
        x|=(1<<b[j])
    fr[x]+=1

min1=int(ma)
max1=int(0)
ind,ind1=int(),int()
for i in range(m):
    b=list(map(int,input().split()))
    x=int(0)
    for j in range(2,b[1]+2):
        b[j]-=1
        x|=(1<<b[j])
    if a[x]!=ma:
        if fr[x]>max1:
            max1=fr[x]
            min1=a[x]+b[0]
            ind=pos[x]
            ind1=i+1
        elif fr[x]==max1:
            if b[0]+a[x]<min1:
                min1=b[0]+a[x]
                ind=pos[x]
                ind1=i+1
    if a[x]>b[0]:
        a[x]=b[0]
        pos[x]=i+1


for i in range(1,512):
    for j in range(1,512):
        if i==j or  a[i]==ma or a[j]==ma:
            continue
        k=i|j
        cnt=int(0)
        while k>0:
            cnt+=fr[k]
            k=(k-1)&(i|j)
        if cnt>max1:
            ind=pos[i]
            ind1=pos[j]
            max1=cnt
            min1=a[i]+a[j]
        if cnt==max1:
            if a[i]+a[j]<min1:
                ind=pos[i]
                ind1=pos[j]
            min1=min(min1,a[i]+a[j])

print(ind,ind1,sep=" ")