//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
// #define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 1e5 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
int n , k , f ;
int len , res ;
ll a[kMaxN] , c[kMaxN][2] ;
int id[kMaxN] ;
int lowbit(int x)
{
	return (x & (-x)) ;
}
ll query(int x , int te)
{
	ll sum = 0 ;
	while(x)
	{
		sum += c[x][te] ;
		x -= lowbit(x) ;
	}
	return sum ;
}
void update(int x , ll v , int k , int te)
{
	while(x <= k)
	{
		c[x][te] += v ;
		x += lowbit(x) ;
	}
}
ll cal(int x)
{
	if(x < 0) return 0 ;
	return x * query(x , 0) - query(x , 1) ;
}
void work()
{
	cin >> n >> k ;
	for( int i(1) ; i <= n ; ++i )
	{
		cin >> a[i] ;
		update(i , a[i] , n , 0) ;
		update(i , 1ll * a[i] * (i - 1) , n , 1) ;
	}
	cin >> f ;
	while(f--)
	{
		int op ;
		cin >> op ;
		if(op == 1)
		{
			for( int i(1) ; i <= k ; ++i )
			{
				cin >> id[i] ;
			}
			int tmp = a[id[1]] ;
			for( int i = 1 ; i < k ; i++ )
			{
				update(id[i] , a[id[i + 1]] - a[id[i]] , n , 0) ;
				update(id[i] , 1ll * (a[id[i + 1]] - a[id[i]]) * (id[i] - 1) , n , 1) ;
				a[id[i]] = a[id[i + 1]] ;
			}
			update(id[k] , tmp - a[id[k]] , n , 0) ;
			update(id[k] , 1ll * (tmp - a[id[k]]) * (id[k] - 1) , n , 1) ;
			a[id[k]] = tmp ;
		}
		else
		{
			int l , r , m ;
			cin >> l >> r >> m ;
			cout << cal(r) - cal(l + m - 2) - (cal(r - m) - cal(l - 2)) << "\n" ;
		}
	}
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}

//Code by hhy
#include<bits/stdc++.h>
#define F(i , a , b , c) for( int i = (a) ; ((c > 0) ? i <= (b) : i >= (b)) ; i += c )
#define T(i , root , b , c) for( int i = root ; b ; c )
// #define int long long
#define W(f) while(f)
#define ull unsigned long long
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std ;
const int kMaxN = 5e4 + 5 , MOD = 998244353 , INF = 1e18 ;
struct Edgepr
{
	int u , w ;
};
struct Edgeve
{
	int v , w ;
};
int n , f ;
int len , res ;
int a[kMaxN] , cnt[kMaxN] , buc[kMaxN] , ans[kMaxN] ;
struct node
{
	int l , r , id , val ;
}Node[kMaxN * 4] ;
bool cmp(node x , node y)
{
	if(x.l / len == y.l / len) 
	{
		if((x.l / len) % 2) return x.r < y.r ;
		return x.r > y.r ;
	}
	return x.l < y.l ;
}
void ADD1(int x)
{
	cnt[a[x]]++ ;
	res += buc[a[x]] ;
}
void SUB1(int x)
{
	cnt[a[x]]-- ;
	res -= buc[a[x]] ;
}
void ADD2(int x)
{
	buc[a[x]]++ ;
	res += cnt[a[x]] ;
}
void SUB2(int x)
{
	buc[a[x]]-- ;
	res -= cnt[a[x]] ;
}
void work()
{
	cin >> n ;
	len = sqrt(n) ;
	for( int i(1) ; i <= n ; ++i )
	{
		cin >> a[i] ;
	}
	cin >> f ;
	int op = 0 ;
	for( int i(1) ; i <= f ; ++i )
	{
		int l1 , r1 , l2 , r2 ;
		cin >> l1 >> r1 >> l2 >> r2 ;
		Node[++op] = {r1 , r2 , i , 1} ;
		Node[++op] = {r1 , l2 - 1 , i , -1} ;
		Node[++op] = {l1 - 1 , r2 , i , -1} ;
		Node[++op] = {l1 - 1 , l2 - 1 , i , 1} ;
	}
	sort(Node + 1 , Node + op + 1 , cmp) ;
	int l = 1 , r = 0 ;
	for( int i(1) ; i <= op ; ++i )
	{
		while(l < Node[i].l) ADD1(++l) ;
		while(l > Node[i].l) SUB1(l--) ;
		while(r < Node[i].r) ADD2(++r) ;
		while(r > Node[i].r) SUB2(r--) ;
		ans[Node[i].id] += Node[i].val * res ;
	}
	for( int i(1) ; i <= f ; ++i ) cout << ans[i] << "\n" ;
}
signed main()
{
//	freopen(".in" , "r" , stdin) ;
//	freopen(".out" , "w" , stdout) ;
//	ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  // cin >> t ;
  while(t--) work() ;
  return 0 ;
}