记录编号	606966	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	4084.魔法卡片	最终得分	100
用户昵称	梦那边的美好TT	是否通过	通过
代码语言	C++	运行时间	5.831 s
提交时间	2025-10-04 19:55:36	内存使用	99.31 MiB

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=2e6+1;
int n,m,Q,a[N],Lg;
LL sum,val[N];
vector<int> v[N];
vector<LL> ans[N];
int read(){
   int x,f=1;
   char ch;
   while(!(isdigit(ch=getchar()))) ch=='-'?f=-1:f;x=ch^48;
   while(isdigit(ch=getchar())) x=(x<<1)+(x<<3)+(ch^48);
   return f*x;
}
int main(){
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
    n=read();
    m=read();
    Q=read();
    Lg=log2(m)+1;
    for(int i=1;i<=m;i++) sum+=1ll*i*i;
    for(int i=1;i<=n;i++){
        v[i].resize(m+2);
        int x=read();
        for(int j=1;j<=x;j++) v[i][read()]=1;
    }
    for(int l=1;l<=n;l++){
        ans[l].resize(Lg+1);
        for(int i=1;i<=m;i++) a[i]=0;
        for(int r=l;r<=min(n,l+Lg);r++){
            for(int i=1;i<=m;i++) a[i]=(a[i]<<1)|v[r][i],val[a[i]]+=1ll*i*i;
            LL res=sum;
            for(int i=0;i<(1<<(r-l+1));i++) res=min(res,val[i]),val[i]=0;
            ans[l][r-l]=sum-res;
        }
    }
    while(Q--){
        int l=read(),r=read();
        if(r-l+1>Lg) printf("%lld\n",sum);
        else printf("%lld\n",ans[l][r-l]);
    }
    return 0;
}