Problem: Note that the memory limit is unusual.

There are n chefs numbered 1, 2, …, n that must prepare dishes for a king. Chef i has skill i and initially has a dish of tastiness a_i where |a_i| ≤ i. Each chef has a list of other chefs that he is allowed to copy from. To stop chefs from learning bad habits, the king makes sure that chef i can only copy from chefs of larger skill.

There are a sequence of days that pass during which the chefs can work on their dish. During each day, there are two stages during which a chef can change the tastiness of their dish. 

  1. At the beginning of each day, each chef can choose to work (or not work) on their own dish, thereby multiplying the tastiness of their dish of their skill (a_i := i ⋅ a_i) (or doing nothing).
  2. After all chefs (who wanted) worked on their own dishes, each start observing the other chefs. In particular, for each chef j on chef i's list, chef i can choose to copy (or not copy) j's dish, thereby adding the tastiness of the j's dish to i's dish (a_i := a_i + a_j) (or doing nothing). It can be assumed that all copying occurs simultaneously. Namely, if chef i chooses to copy from chef j he will copy the tastiness of chef j's dish at the end of stage 1.



All chefs work to maximize the tastiness of their own dish in order to please the king.

Finally, you are given q queries. Each query is one of two types.

  1. 1 k l r — find the sum of tastiness a_l, a_{l+1}, …, a_{r} after the k-th day. Because this value can be large, find it modulo 10^9 + 7. 
  2. 2 i x — the king adds x tastiness to the i-th chef's dish before the 1-st day begins (a_i := a_i + x). Note that, because the king wants to see tastier dishes, he only adds positive tastiness (x > 0). 



Note that queries of type 1 are independent of each all other queries. Specifically, each query of type 1 is a scenario and does not change the initial tastiness a_i of any dish for future queries. Note that queries of type 2 are cumulative and only change the initial tastiness a_i of a dish. See notes for an example of queries.

Input

The first line contains a single integer n (1 ≤ n ≤ 300) — the number of chefs.

The second line contains n integers a_1, a_2, …, a_n (-i ≤ a_i ≤ i).

The next n lines each begin with a integer c_i (0 ≤ c_i < n), denoting the number of chefs the i-th chef can copy from. This number is followed by c_i distinct integers d (i < d ≤ n), signifying that chef i is allowed to copy from chef d during stage 2 of each day.

The next line contains a single integer q (1 ≤ q ≤ 2 ⋅ 10^5) — the number of queries.

Each of the next q lines contains a query of one of two types: 

  * 1 k l r (1 ≤ l ≤ r ≤ n; 1 ≤ k ≤ 1000); 
  * 2 i x (1 ≤ i ≤ n; 1 ≤ x ≤ 1000). 



It is guaranteed that there is at least one query of the first type.

Output

For each query of the first type, print a single integer — the answer to the query.

Example

Input


5
1 0 -2 -2 4
4 2 3 4 5
1 3
1 4
1 5
0
7
1 1 1 5
2 4 3
1 1 1 5
2 3 2
1 2 2 4
2 5 1
1 981 4 5


Output


57
71
316
278497818

Note

Below is the set of chefs that each chef is allowed to copy from:

  * 1: \{2, 3, 4, 5\} 
  * 2: \{3\} 
  * 3: \{4\} 
  * 4: \{5\} 
  * 5: ∅ (no other chefs)



Following is a description of the sample.

For the first query of type 1, the initial tastiness values are [1, 0, -2, -2, 4].

The final result of the first day is shown below: 

  1. [1, 0, -2, -2, 20] (chef 5 works on his dish). 
  2. [21, 0, -2, 18, 20] (chef 1 and chef 4 copy from chef 5). 



So, the answer for the 1-st query is 21 + 0 - 2 + 18 + 20 = 57.

For the 5-th query (3-rd of type 1). The initial tastiness values are now [1, 0, 0, 1, 4].

Day 1

  1. [1, 0, 0, 4, 20] (chefs 4 and 5 work on their dishes). 
  2. [25,0, 4, 24, 20] (chef 1 copies from chefs 4 and 5, chef 3 copies from chef 4, chef 4 copies from chef 5). 



Day 2

  1. [25, 0, 12, 96, 100] (all chefs but chef 2 work on their dish). 
  2. [233, 12, 108, 196, 100] (chef 1 copies from chefs 3, 4 and 5, chef 2 from 3, chef 3 from 4, chef 4 from chef 5).

So, the answer for the 5-th query is 12+108+196=316. 




It can be shown that, in each step we described, all chefs moved optimally.

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define pb push_back
using namespace std;

//#define DEBUG
#ifdef DEBUG
template<typename ...Args>
int debug(const Args &...args){
	return fprintf(stderr,args...);
}
#else
#define debug(...) void()
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
#define G getchar()
int read()
{
	int x=0; bool flg=false; char ch=G;
	for (;!isdigit(ch);ch=G) if (ch=='-') flg=true;
	for (;isdigit(ch);ch=G) x=(x<<3)+(x<<1)+(ch^48);
	return flg?-x:x;
}
#undef G
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
//typedef pair<int,int> P;
const int mod=1e9+7;
inline int upd(const int &x){return x+(x>>31&mod);}
inline void add(int &x,const int &y){x=upd(x+y-mod);}
inline void iadd(int &x,const int &y){x=upd(x-y);}
int qpow(int x,int y){
	int res=1;
	for (;y;y>>=1,x=1LL*x*x%mod)
		if (y&1) res=1LL*res*x%mod;
	return res;
}
#define rep(i,l,r) for (int i(l),_##i(r);i<=_##i;i++)
#define per(i,l,r) for (int i(r),_##i(l);i>=_##i;i--)
#define forall(x,y) for (const int &y: e[x])
#define ctz __builtin_ctz

int n,q,h[310]; const int m=1000;
bool mp[310][310];

namespace LA{

int a[310][310],V[310][310];

void gauss0(int n,int a[][310],int *V,int o){
	per(i,1,n)
		if (i^o){
			int &z=V[i];
			rep(j,i+1,n) iadd(z,1LL*a[i][j]*V[j]%mod);
			z=1LL*z*qpow(a[i][i],mod-2)%mod;
		}
		else V[i]=1;
}

int b[310][310],c[310][310],s[310][310],d[310][310],_c[310][310];

void gauss1(int n,int a[][310],int b[][310],int c[][310]){
	rep(i,1,n){
		int p=-1;
		rep(j,i,n) if (a[j][i]) {p=j; break;}
		assert(~p);
		if (p^i){
			rep(j,1,n){
				swap(a[p][j],a[i][j]);
				swap(b[p][j],b[i][j]);
				swap(c[p][j],c[i][j]);
			}
		}
		const int t=qpow(a[i][i],mod-2);
		rep(j,1,n){
			a[i][j]=1LL*a[i][j]*t%mod;
			b[i][j]=1LL*b[i][j]*t%mod;
			c[i][j]=1LL*c[i][j]*t%mod;
		}
		rep(j,1,n) if (j^i&&a[j][i]){
			const int s=1LL*a[j][i]*t%mod;
			rep(k,1,n){
				iadd(a[j][k],1LL*a[i][k]*s%mod);
				iadd(b[j][k],1LL*b[i][k]*s%mod);
				iadd(c[j][k],1LL*c[i][k]*s%mod);
			}
		}
	}
}

}
using namespace LA;

void prepare(){
	rep(i,1,n){
		rep(u,1,n) rep(v,1,n)
			a[u][v]=u==v||mp[v][u]?v:0;
		rep(j,1,n) iadd(a[j][j],i);
		LA::gauss0(n,a,V[i],i);  // row
	}
	rep(i,1,n) rep(j,1,n) a[i][j]=V[j][i],d[i][j]=i==j||mp[j][i]?j:0,_c[i][j]=i==j;
	
	LA::gauss1(n,a,d,_c);
	
	rep(i,1,n) rep(j,1,n) rep(k,1,n) add(b[i][j],1LL*d[i][k]*V[j][k]%mod);
	memcpy(c,_c,sizeof c);
	
	rep(i,1,n) rep(j,1,n) if (b[i][j]) assert(i==j);
	rep(i,1,n) rep(j,1,n) s[i][j]=V[i][j],add(s[i][j],s[i][j-1]);
}

int dp[310];
int tri[1010][310];
int pw[32][310];

void build(){
	fill(dp+1,dp+n+1,m+1);
	per(i,1,n){
		if (h[i]>0) dp[i]=1;
		else if (dp[i]>m) continue;
		rep(j,1,i-1) if (mp[i][j]) dp[j]=min(dp[j],dp[i]+1);
	}
	rep(i,1,n){
		pw[0][i]=b[i][i];
		rep(j,1,10) pw[j][i]=1LL*pw[j-1][i]*pw[j-1][i]%mod;
	}
	memset(tri,0,sizeof tri);
	rep(i,1,n) if (dp[i]<=m){
		rep(j,1,n){
			add(tri[dp[i]][j],1LL*pw[0][j]*c[j][i]%mod*upd(h[i])%mod);
		}
	}
	rep(i,1,m){
		const int j=i+(i&-i),k=ctz(i);
		if (j>m) continue;
		const auto F=tri[i],H=pw[k]; auto G=tri[j];
		rep(t,1,n) add(G[t],1LL*F[t]*H[t]%mod);
	}
}

void update(int x,int w){
	static int f[310];
	rep(i,1,n) f[i]=1LL*c[i][x]*w%mod*pw[0][i]%mod;
	for (x=dp[x];x<=m;x+=x&-x){
		auto F=tri[x];
		rep(j,1,n) add(F[j],f[j]);
		const auto G=pw[ctz(x)];
		rep(j,1,n) f[j]=1LL*f[j]*G[j]%mod;
	}
}

int query(int o,int l,int r){
	static int g[310],h[310];
	rep(i,1,n) h[i]=1,g[i]=0;
	int z=0;
	rep(i,l,r) if (dp[i]>o) add(z,upd(::h[i]));
	for (;o;o-=o&-o){
		const auto F=tri[o];
		rep(i,1,n) add(g[i],1LL*h[i]*F[i]%mod);
		const int k=ctz(o); const auto G=pw[k];
		rep(i,1,n) h[i]=1LL*h[i]*G[i]%mod;
	}
	rep(i,1,n) add(z,1LL*(s[i][r]-s[i][l-1]+mod)*g[i]%mod);
	return z;
}

void solve(){
	#define a h
	n=read();
	rep(i,1,n) a[i]=read();
	rep(i,1,n){
		int g=read();
		while (g--) mp[read()][i]=1;
	}
	prepare();
	build();
	q=read();
	while (q--){
		if (read()&1){
			int k=read(),l=read(),r=read();
			printf("%d\n",query(k,l,r));
		}
		else{
			int x=read(),w=read();
			a[x]+=w;
			if (a[x]-w<=0&&a[x]>0) build();
			else if (dp[x]<=m) update(x,w);
		}
	}
}

int main()
{
	for (int T=1;T--;) solve();
	return 0;
}