2

给出 \(N\) 个已经塞了数进去的栈（每个栈中元素的数量可能不同），有一个空的「答案队列」，你每次可以「将一个栈的栈顶元素弹出，插入答案队列的末尾」，直至所有栈都清空。试求「字典序最小」的答案队列。

如果两个答案队列 \(a,b\)（从队首往队尾数）前\(i?1\) 个数都相同，而\(a_i ，则我们称 \(a\) 的字典序比 \(b\) 的字典序小。

输入格式
第一行一个整数\(N\) 。 接下来 \(N\) 行，每行第一个整数为\(L\) ，表示栈中元素的数量。接下来按照从栈顶到栈底的顺序依次给出 \(L\) 个整数。

输出格式
\(∑L\)个整数，表示字典序最小的答案队列。

样例1
input

3
1 2
1 100
1 1

output

1 2 100

样例2
input

2
3 5 1 2
3 5 1 1

output

5 1 1 5 1 2

数据范围
\(1≤N≤1000,1≤L≤1000\)。

时间限制：2S

空间限制：256MB

按照贪心，肯定是尽量先选小的。考虑把所有的序列塞到一个堆里，然后按照首个数字排序每次取出首位数字最小的数字，然后把最小的弹掉之后再塞回堆里。

看样例，我们会发现一个问题：如果首位数字相同，谁更先取出呢？肯定是第二位小的先取出，因为我们可以更快去到1个小的数。但如果第二位也相同呢，我们就要比较第三位，第四位，直到有一位不同或有一个栈没有数了。如果有个没有数了，那肯定优先选有数的那个栈。

这样比较复杂度很高，所以我们可以预处理出栈的哈希值,方法类似字符串哈希，通过二分去看到底有前几位是相同的，然后找到第一位不相同的数，判断哪个大哪个小。

#include
#include
using namespace std;
const int N=1005;
const long long P=1e9+7,Q=100000001;
int a[N][N],n,s[N];
long long ans,pw[N],f[N][N];
long long hash(int x,int l,int r)
{
	return (f[x][r]-f[x][l-1]*pw[r-l+1]%P+P)%P;
}
struct node{
	int x,y;
	bool operator<(const node&n)const{
		int l=0,r=min(s[x]-y,s[n.x]-n.y);
		while(l<=r)
		{
			int md=(l+r)>>1;
			if(hash(x,y,y+md)==hash(n.x,n.y,n.y+md))
				l=md+1;
			else
				r=md-1;
		}
		return a[x][y+l]>a[n.x][n.y+l];
	}
};
priority_queueq;
int main()
{
	scanf("%d",&n),pw[0]=1;
	for(int i=1;i<=1000;i++)
		pw[i]=Q*pw[i-1]%P;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",s+i);
		for(int j=1;j<=s[i];j++)
			scanf("%d",a[i]+j);
		for(int j=1;j<=s[i];j++)
			f[i][j]=(Q*f[i][j-1]+a[i][j])%P;
		a[i][s[i]+1]=2147483647;
		q.push((node){i,1});
	}
	while(!q.empty())
	{
		node k=q.top();
		q.pop();
		printf("%d ",a[k.x][k.y]);
		if(s[k.x]!=k.y)
			q.push((node){k.x,k.y+1});
	}
}