数据范围分治。沿用题目中的变量意义。设 \(K = \Pi k_i\),即我们总共有 \(K\) 种组合情况,当 \(K\) 比较小的时候,直接枚举每个集合得到的余数是哪个,然后做 CRT 记录后排序答案即可。当 \(K\) 比较大的时候,随几组数据能够发现解的分布较为稠密,考虑任选一个限制条件,答案一定要形如 \(\lambda X + y\),枚举 \(\lambda\) 和 \(y\),然后判断得到的解是否能够符合所有条件。那么取哪一个限制条件比较好呢,那必然是让 \(X\) 尽可能大,\(k\) 尽可能小,这样遍历到的数更为连续,这样我们选择 \(\dfrac{k}{X}\) 最小的那个限制。取一个合适的阈值,小的时候做 CRT,过大时暴力枚举即可。
#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define power(x) ((x)*(x))
#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) (x/gcd(x,y)*y)
#define lg(x,y) __lg(x,y)
using namespace std;
template<typename T=int> inline T read()
{
T s=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
return s*w;
}
template<typename T=int> inline void write(T x,char ch)
{
if(x<0) x=-x,putchar('-');
static char stk[25]; int top=0;
do {stk[top++]=x%10+'0',x/=10;} while(x);
while(top) putchar(stk[--top]);
putchar(ch);
return;
}
namespace MyTool
{
static const int Mod=998244353;
template<typename T> inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
template<typename T> inline void cmax(T &a,T b) {a=a>b?a:b;}
template<typename T> inline void cmin(T &a,T b) {a=a<b?a:b;}
template<typename T> inline void Madd(T &a,T b) {a=a+b>Mod?a+b-Mod:a+b;}
template<typename T> inline void Mdel(T &a,T b) {a=a-b<0?a-b+Mod:a-b;}
template<typename T> inline void Mmul(T &a,T b) {a=a*b%Mod;}
template<typename T> inline void Mmod(T &a) {a=(a%Mod+Mod)%Mod;}
template<typename T> inline T Cadd(T a,T b) {return a+b>=Mod?a+b-Mod:a+b;}
template<typename T> inline T Cdel(T a,T b) {return a-b<0?a-b+Mod:a-b;}
template<typename T> inline T Cmul(T a,T b) {return a*b%Mod;}
template<typename T> inline T Cmod(T a) {return (a%Mod+Mod)%Mod;}
inline int qpow(int a,int b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
inline int qmul(int a,int b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
inline int Qpow(int a,int b) {int res=1; while(b) {if(b&1) res=qmul(res,a); a=qmul(a,a); b>>=1;} return res;}
}
using namespace MyTool;
inline void file()
{
freopen(".in","r",stdin);
freopen(".out","w",stdout);
return;
}
bool Mbe;
namespace LgxTpre
{
static const int MAX=15;
static const int inf=2147483647;
static const int INF=4557430888798830399;
static const int mod=1e9+7;
static const int bas=131;
int n,T,x;
int all,num[MAX],M,m[MAX],inv[MAX];
vector<int> s[MAX],ans;
unordered_map<int,bool> vis[MAX];
static const int top=10000;
void exgcd(int a,int b,int &x,int &y,int &tmp)
{
if(!b) return x=1,y=0,tmp=a,void();
exgcd(b,a%b,y,x,tmp),y-=x*(a/b);
}
inline int get_inv(int K,int mod)
{
int x=0,y=0,tmp=0;
exgcd(K,mod,x,y,tmp);
return (x%mod+mod)%mod;
}
inline void solve1()
{
int use=1;
for(int i=2;i<=n;++i) if(m[i]*num[use]>m[use]*num[i]) use=i;
for(int k=0;((int)ans.size())<T;++k) for(int i=0;i<num[use]&&((int)ans.size())<T;++i)
{
int now=k*m[use]+s[use][i]; if(!now) continue;
int flag=0;
for(int j=1;j<=n;++j) if(!vis[j][now%m[j]]) {flag=1; break;}
if(!flag) ans.eb(now);
}
}
inline void solve2()
{
M=1;
for(int i=1;i<=n;++i) M*=m[i];
for(int i=1;i<=n;++i) inv[i]=M/m[i]*get_inv(M/m[i],m[i]);
for(int S_=0;S_<all;++S_)
{
int S=S_,x=0;
for(int i=1;i<=n;++i) x=(x+s[i][S%num[i]]*inv[i]%M)%M,S/=num[i];
ans.eb(x?x:x+M);
}
sort(ans.begin(),ans.end());
ans.resize(unique(ans.begin(),ans.end())-ans.begin());
for(int i=0;((int)ans.size())<T;++i) ans.eb(ans[i]+M);
}
inline void mian()
{
do
{
for(int i=1;i<=n;++i) s[i].clear(),vis[i].clear();
n=read(),T=read(),all=1;
if(!n&&!T) break;
for(int i=1;i<=n;++i)
{
m[i]=read(),num[i]=read(),all*=num[i];
for(int j=1;j<=num[i];++j) x=read(),s[i].eb(x),vis[i][x]=1;
sort(s[i].begin(),s[i].end());
}
ans.clear();
all>=top?solve1():solve2();
for(int i=0;i<T;++i) write(ans[i],'\n'); puts("");
}while(true);
return;
}
}
bool Med;
signed main()
{
// file();
fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
int Tbe=clock();
LgxTpre::mian();
int Ted=clock();
cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
return (0-0);
}