#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3;
const LL inf=1e18;
int n,m,x,y,w,l,r,o,op,st,head[N<<3];bool pan[N<<3];LL dis[N<<3];
struct QAQ{int w,to,next;}a[(N<<3)+(N<<2)+N*18*2];
inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
int O;
struct QAQ{int in,out;}tr[N<<2];
inline void build(Re p,Re L,Re R){
if(L==R){tr[p].in=tr[p].out=L;return;}
tr[p].in=++O,tr[p].out=++O,add(tr[p].in,tr[p].out,0);
build(pl,L,mid),build(pr,mid+1,R);
add(tr[p].in,tr[pl].in,0),add(tr[p].in,tr[pr].in,0);
add(tr[pl].out,tr[p].out,0),add(tr[pr].out,tr[p].out,0);
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re w,Re op){
if(l<=L&&R<=r){
if(op)add(tr[p].out,x,w);
else add(x,tr[p].in,w);
return;
}
if(l<=mid)change(pl,L,mid,l,r,x,w,op);
if(r>mid)change(pr,mid+1,R,l,r,x,w,op);
}
}TR;
struct QWQ{int x;LL d;inline bool operator<(const QWQ &O)const{return d>O.d;}};
priority_queue<QWQ>Q;
inline void dijkstra(Re st){
for(Re i=1;i<=TR.O;++i)dis[i]=inf;
Q.push((QWQ){st,dis[st]=0});
while(!Q.empty()){
Re x=Q.top().x;Q.pop();
if(pan[x])continue;
pan[x]=0;
for(Re i=head[x],to;i;i=a[i].next)
if(dis[to=a[i].to]>dis[x]+a[i].w)
Q.push((QWQ){to,dis[to]=dis[x]+a[i].w});
}
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),in(st);
TR.O=n,TR.build(1,1,n);
while(m--){
in(op),in(x);
if(op<2)in(y),in(w),TR.change(1,1,n,y,y,x,w,0);
else if(op<3)in(l),in(r),in(w),TR.change(1,1,n,l,r,x,w,0);
else in(l),in(r),in(w),TR.change(1,1,n,l,r,x,w,1);
}
dijkstra(st);
for(Re i=1;i<=n;++i)printf("%lld ",dis[i]==inf?-1:dis[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define LL long long
#define Re register int
using namespace std;
const int N=5003+3,M=25e4+3,inf=2e9;
int n,m,x,y,z,O,op,st,ed,X[N],Y[N],Z[N],Ans[N],cnt[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Network_Flow{
int o,h,t,maxflow,Q[N*3],dis[N*3],cur[N*3],head[N*3];
struct QAQ{int to,next,flow;}a[M<<1];
inline void add_(Re x,Re y,Re flow){a[++o].to=y,a[o].flow=flow,a[o].next=head[x],head[x]=o;}
inline void add(Re x,Re y,Re flow){add_(x,y,flow),add_(y,x,0);}
inline int bfs(Re st,Re ed){
for(Re i=0;i<=ed;++i)dis[i]=0,cur[i]=head[i];
h=1,t=0,dis[Q[++t]=st]=1;
while(h<=t){
Re x=Q[h++];
for(Re i=head[x],to;i;i=a[i].next)
if(a[i].flow&&!dis[to=a[i].to]){
dis[Q[++t]=to]=dis[x]+1;
if(to==ed)return 1;
}
}
return 0;
}
inline int dfs(Re x,Re flow){
if(x==ed||!flow)return flow;
Re tmp=0,to,f;
for(Re i=cur[x];i;i=a[i].next){
cur[x]=i;
if(dis[to=a[i].to]==dis[x]+1&&(f=dfs(to,min(a[i].flow,flow-tmp)))){
a[i].flow-=f,a[i^1].flow+=f,tmp+=f;
if(tmp==flow)break;
}
}
return tmp;
}
inline void dinic(Re st,Re ed){while(bfs(st,ed))maxflow+=dfs(st,inf);}
inline int find(Re x){
Re last=ed;
while(x<=O||x>O+n){
for(Re i=head[x];i;i=a[i].next)
if(a[i^1].to==x&&a[i].to!=last&&a[i].flow){
--a[i].flow,last=x,x=a[i].to;break;
}
}
return x-O;
}
}T1;
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
struct QAQ{int in;}tr[N<<2];
inline void build(Re p,Re L,Re R){
if(L==R){tr[p].in=L;return;}
tr[p].in=++O,build(pl,L,mid),build(pr,mid+1,R);
T1.add(tr[p].in,tr[pl].in,inf),T1.add(tr[p].in,tr[pr].in,inf);
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re x,Re w){
if(l<=L&&R<=r){T1.add(x,tr[p].in,w);return;}
if(l<=mid)change(pl,L,mid,l,r,x,w);
if(r>mid)change(pr,mid+1,R,l,r,x,w);
}
}TR;
int main(){
// freopen("123.txt","r",stdin);
in(n),in(m),T1.o=1,O=m,TR.build(1,1,m),st=O+n+1,ed=st+1;
for(Re i=1;i<=n;++i){
in(op);
if(op<1){
in(x),T1.add(st,O+i,1);
while(x--)in(y),T1.add(O+i,y,1);
}
else if(op<2)in(x),in(y),T1.add(st,O+i,1),TR.change(1,1,m,x,y,O+i,1);
else{
in(x),in(y),in(z),T1.add(st,O+i,2),X[i]=x,Y[i]=y,Z[i]=z;
T1.add(O+i,x,1),T1.add(O+i,y,1),T1.add(O+i,z,1);
}
}
for(Re j=1;j<=m;++j)T1.add(j,ed,1);
T1.dinic(st,ed),printf("%d\n",T1.maxflow);
for(Re i=T1.head[ed];i;i=T1.a[i].next)
if(T1.a[i].flow)++cnt[Ans[T1.a[i].to]=T1.find(T1.a[i].to)];
for(Re i=1;i<=n;++i)
if(X[i]&&cnt[i]==1){
if(Ans[X[i]]==i)Ans[Y[i]]=i;
else Ans[X[i]]=i;
}
for(Re i=1;i<=m;++i)if(Ans[i])printf("%d %d\n",Ans[i],i);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<map>
#define LL long long
#define Re register int
#define mp make_pair
using namespace std;
const int N=5e5+3,M=(N<<2)+N*18*2,P=1e9+7;
int o,n,Ans,head[N<<2];LL X[N],R[N];
struct QAQ{int x,to,next;}a[M];map<pair<int,int>,int>vis;
inline void add(Re x,Re y){a[++o].x=x,a[o].to=y,a[o].next=head[x],head[x]=o;}
template<typename T>inline void in(T &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
struct Segment_Tree{
#define pl (p<<1)
#define pr (p<<1|1)
#define mid ((L+R)>>1)
int O;
struct QAQ{int in;}tr[N<<2];
inline void build(Re p,Re L,Re R){
if(L==R){tr[p].in=L;return;}
tr[p].in=++O;
build(pl,L,mid),build(pr,mid+1,R);
add(tr[p].in,tr[pl].in),add(tr[p].in,tr[pr].in);
}
inline void change(Re p,Re L,Re R,Re l,Re r,Re x){
// printf("(x=%d) -> (l=%d,r=%d) w=%d\n",x,l,r,w);return;
if(l<=L&&R<=r){add(x,tr[p].in);return;}
if(l<=mid)change(pl,L,mid,l,r,x);
if(r>mid)change(pr,mid+1,R,l,r,x);
}
}TR;
inline int find1(LL x,Re r){
Re l=1;
while(l<r){
Re Mid=l+r>>1;
if(X[Mid]<x)l=Mid+1;
else r=Mid;
}
return r;
}
inline int find2(LL x,Re l){
Re r=n;
while(l<r){
Re Mid=l+r+1>>1;
if(X[Mid]>x)r=Mid-1;
else l=Mid;
}
return l;
}
struct Tuopu{
int o,n,L[N<<2],R[N<<2],ru[N<<2],pan[N<<2],head[N<<2];queue<int>Q;
struct QAQ{int to,next;}a[M];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void dfs(Re x){
if(pan[x])return;
pan[x]=1;
for(Re i=head[x],to;i;i=a[i].next)
dfs(to=a[i].to),L[x]=min(L[x],L[to]),R[x]=max(R[x],R[to]);
}
inline void sakura(){for(Re i=1;i<=n;++i)if(!ru[i])dfs(i);}
}T2;
int Q_o,ip[N<<2];
struct Tarjan{
int n,t,dfn_o,Q[N<<2],low[N<<2],dfn[N<<2],pan[N<<2];
inline void tarjan(Re x){
dfn[x]=low[x]=++dfn_o,Q[++t]=x,pan[x]=1;
for(Re i=head[x],to;i;i=a[i].next)
if(!dfn[to=a[i].to])tarjan(to),low[x]=min(low[x],low[to]);
else if(pan[to])low[x]=min(low[x],dfn[to]);
if(low[x]==dfn[x]){
++Q_o,T2.L[Q_o]=n+1,T2.R[Q_o]=-1;
while(1){
ip[Q[t]]=Q_o,pan[Q[t]]=0;
if(x==Q[t--])break;
}
}
}
inline void sakura(){
for(Re i=1;i<=n;++i)if(!dfn[i])tarjan(i);
for(Re i=1,x,y;i<=o;++i)
if((x=ip[a[i].x])!=(y=ip[a[i].to])&&!vis[mp(x,y)])
vis[mp(x,y)]=1,++T2.ru[y],T2.add(x,y);
}
}T1;
int main(){
// freopen("123.txt","r",stdin);
in(n),TR.O=n,TR.build(1,1,n);
for(Re i=1;i<=n;++i)in(X[i]),in(R[i]);
for(Re i=1;i<=n;++i)TR.change(1,1,n,find1(X[i]-R[i],i),find2(X[i]+R[i],i),i);
T1.n=TR.O,T1.sakura();
for(Re i=1;i<=n;++i)T2.L[ip[i]]=min(T2.L[ip[i]],i),T2.R[ip[i]]=max(T2.R[ip[i]],i);;
T2.n=Q_o,T2.sakura();
for(Re i=1;i<=n;++i)(Ans+=(LL)i*(T2.R[ip[i]]-T2.L[ip[i]]+1)%P)%=P;
printf("%d\n",Ans);
}