To confuse the opponents, the Galactic Empire represents fractions in an unusual format. The fractions are represented as two sets of integers. The product of numbers from the first set gives the fraction numerator, the product of numbers from the second set gives the fraction denominator. However, it turned out that the programs that work with fractions in this representations aren't complete, they lack supporting the operation of reducing fractions. Implement this operation and the Empire won't forget you.
The first input line contains two space-separated integers *n*, *m* (1 ≤ *n*, *m* ≤ 10<sup class="upper-index">5</sup>) that show how many numbers the first set (the numerator) and the second set (the denominator) contain, correspondingly.

The second line contains *n* space-separated integers: *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">7</sup>) — the numbers that are multiplied to produce the numerator.

The third line contains *m* space-separated integers: *b*<sub class="lower-index">1</sub>, *b*<sub class="lower-index">2</sub>, ..., *b*<sub class="lower-index">*m*</sub> (1 ≤ *b*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">7</sup>) — the numbers that are multiplied to produce the denominator.
/*
* Filename:    d.cpp
* Created:     2016年08月20日 21时39分01秒 星期六
* Author:      JIngwei Xu [mail:[email protected]]
*
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include <cstdarg>
#include <bitset>
using namespace std;

#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i = 0; i < n; i++)
#define re return
#define fi first
#define se second
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define sqr(x) ((x) * (x))
#define clr(a,b) (memset(a,b,sizeof(a)))
#define y0 y3487465
#define y1 y8687969


typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef vector<vi> vvi;

inline int read()
{    
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

template<class T> T abs(T x) {
	re x > 0 ? x : -x;
}

template<class T> T gcd(T a,T b) {
	re b==0?a:gcd(b,a%b);
}

//Init Const
const int INF=1e9;
const int MOD=1e9+7;
const int maxn=1000+7;
const int maxq=1e5+7;
//Global Variables
int n,m,t,T;
int ans[maxq];

struct node{
	int type,v1,v2;
}Q[maxq];

vector<int> G[maxq];

//Function Declaration
int a,b,q,k;
void update(int rt,int type,int v1=0,int v2=0){
	Q[rt].type=type;
	Q[rt].v1=v1;
	Q[rt].v2=v2;
	if(type==4)G[v1].pb(rt);
	else G[rt-1].pb(rt);
}

bitset<maxn> bit[maxn];
int vis[maxn];

void dfs(int i,int res){
	ans[i]=res;
	int w=G[i].size();
	for(int j=0;j<w;j++){
		int next=G[i][j];
		if(Q[next].type==1){
			int a=Q[next].v1-1,b=Q[next].v2-1;
			if(bit[a][b]==0){
				bit[a][b]=1;
				dfs(next,res+1);
				bit[a][b]=0;
			}else dfs(next,res);
			
		}else if(Q[next].type==2){
			int a=Q[next].v1-1,b=Q[next].v2-1;
			if(bit[a][b]==1){
				bit[a][b]=0;
				dfs(next,res-1);
				bit[a][b]=1;
			}else dfs(next,res);
			
		}else if(Q[next].type==3){
			int ads=maxn-m;
			int a=Q[next].v1-1;
			int tmp=bit[a].count();
			if(vis[a])tmp-=ads;
			bit[a].flip();
			vis[a]=1-vis[a];
			tmp-=bit[a].count();
			if(vis[a])tmp+=ads;
			
			dfs(next,res-tmp);
			bit[a].flip();
			vis[a]=1-vis[a];
			
		}else dfs(next,res);
	}
}
//Main Program
int main()
{
#ifdef AC_THIS_PROBLEM
	freopen("in.txt","r",stdin);
	//freopen("data/data.out","w",stdout);
#endif
	update(0,0);
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=q;i++){
		scanf("%d",&t);
		if(t==1||t==2){
			scanf("%d%d",&a,&b);
			update(i,t,a,b);
		}else if(t==3){
			scanf("%d",&a);
			update(i,t,a);
		}else if(t==4){
			scanf("%d",&a);
			update(i,t,a);
		}
	}
	clr(vis,0);
	dfs(0,0);
	for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
	return 0;
}
