描述#

硬盘中里面有n个文件，文件从1到n标号，每个文件可以用若干个数字序列来表示，而且每个文件存在一个重要值。现在请你完成一个搜索系统，有m 个搜索的操作，如果一个文件中有以这个数字序列为前缀的数字序列，那么这个文件会被搜索到，现在我们想知道会有多少个文件被搜索到，以及这 些文件中重要值前k小的是哪些。

输入#

第一行两个数n,m。 接下来n行是对每个文件的描述（标号依次是1到n）： 每行的前两个数字分别为描述这个文件的数字序列个数t和文件的重要值v。 接下来有t组数。 每组数先有一个数l，表示这个数字序列的长度。 接下来有l个数，表示这个序列。 接下来m行表示m个搜索操作： 每行的前两个数字分别为搜索数k和前缀长度l。 接下来l个数是这个前缀的数字序列。

输出#

共m行。 每行来表示搜索的结果： 首先你需要输出有多少个文件会被搜索到。 接下来你需要输出k个数，依次是重要值前k小的标号（根据重要值由小到大输出，重要值相同时，标号小的排在前面）。 如果搜索到的文件数p比k小，那么你只需要输出p个,如果没有搜索到文件就不用输出了。

样例输入#

5 5
1 1 5 1 2 3 4 5
1 2 5 1 2 4 5 3
1 8 5 2 1 4 3 2
1 9 5 2 1 8 5 2
1 1 5 1 2 3 4 5
2 2 1 2
3 2 1 2
4 2 1 2
4 2 2 1
1 2 2 1

样例输出#

3 1 5
3 1 5 2
3 1 5 2
2 3 4
2 3

数据范围和约定#

• 对于20%的数据
  0<n,m<=50
  每次询问k无限制
  0<重要值<=10^9
  0<数字序列中的数字<=10
  所有文件数字序列长度之和<=500
  所有询问前缀数字序列长度之和<=500
• 对于另外20%的数据
  0<n,m<=50
  每次询问k无限制
  0<重要值<=10^9
  0<数字序列中的数字<=10^9
  所有文件数字序列长度之和<=500
  所有询问前缀数字序列长度之和<=500
• 对于另外20%的数据
  0<n,m<=510^4
  每次询问k=1或k=2
  0<重要值<=10^9
  0<数字序列中的数字<=10
  所有文件数字序列长度之和<=210^5
  所有询问前缀数字序列长度之和<=2*10^5
• 对于剩下的数据
  0<n,m<=510^4
  每次询问k无限制
  0<重要值<=10^9
  0<数字序列中的数字<=10^9
  所有文件数字序列长度之和<=210^5
  所有询问前缀数字序列长度之和<=2*10^5

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <ctime>
using namespace std;
vector<int> l;
struct Improtant
{
    int i, Imp;
    bool operator<(const Improtant &a) const
    {
        return Imp == a.Imp ? i < a.i : Imp < a.Imp;
    }
} number[50005];
struct Trie
{
    map<int, Trie *> mp;
    set<Improtant> mark;
} * root;
void insert(int x)
{
    Trie *rt = root;
    rt->mark.insert(number[x]);
    for (int i = 0; i < l.size(); i++)
    {
        if (!rt->mp[l[i]])
            rt->mp[l[i]] = new Trie;
        rt = rt->mp[l[i]];
        rt->mark.insert(number[x]);
    }
}
void Query(int k)
{
    Trie *rt = root;
    for (int i = 0; i < l.size(); i++)
    {
        if (rt->mp[l[i]] == NULL)
        {
            printf("0\n");
            return;
        }
        rt = rt->mp[l[i]];
    }
    set<Improtant>::iterator it = rt->mark.begin();
    printf("%d ", rt->mark.size());
    for (int i = 1; i <= k && it != rt->mark.end(); i++, it++)
    {
        printf("%d ", it->i);
    }
    printf("\n");
    return;
}
int main()
{
#ifdef Mine
    freopen("1.in", "r", stdin);
#else
    freopen("string.in", "r", stdin);
#endif
    freopen("string.out", "w", stdout);
    int n, m;
    root = new Trie;
    scanf("%d%d", &n, &m);
    int t, s, a;
    for (int i = 1; i <= n; i++)
    {
        number[i].i = i;
        scanf("%d%d", &t, &number[i].Imp);
        while (t--)
        {
            scanf("%d", &s);
            l.clear();
            for (int j = 1; j <= s; j++)
            {
                scanf("%d", &a);
                l.push_back(a);
            }
            insert(i);
        }
    }
    int k;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &k, &s);
        l.clear();
        for (int j = 1; j <= s; j++)
        {
            scanf("%d", &a);
            l.push_back(a);
        }
        Query(k);
    }
    //printf("%lf",(double)clock()/CLOCKS_PER_SEC);
}