#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=(1LL<<60)-1;
ll a[55],b[55];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=1;i<=m;i++)
        scanf("%lld",&b[i]);
    ll res=INF;
    for(int i=1;i<=n;i++)
    {
        ll now=-INF;
        for(int j=1;j<=n;j++)if(j!=i)
            for(int k=1;k<=m;k++)
                now=max(now,a[j]*b[k]);
        res=min(res,now);
    }
    printf("%lld\n",res);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n,k;
int main()
{
	scanf("%d",&k);
	if (k>36) printf("%d\n",-1);
	else
	{
		while (k>0)
		{
			if (k>=2)
			{
				printf("%d",8);
				k-=2;
			} else
			{
				printf("%d",9);
				k-=1;
			}
		}
		printf("\n");
	}
	return 0;
}

#include <bits/stdc++.h>

#define rep(i, x, y) for (int i = (x), _ = (y); i < _; ++i)
#define down(i, x, y) for (int i = (x) - 1, _ = (y); i >= _; --i)
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define bin(x) (1 << (x))
#define SZ(x) int((x).size())

using namespace std;
typedef pair<int, int> pii;
typedef vector<int> Vi;
typedef long long ll;

template<typename T> inline bool upmax(T &x, T y) { return x < y ? (x = y, 1) : 0; }
template<typename T> inline bool upmin(T &x, T y) { return x > y ? (x = y, 1) : 0; }

const int MAX_N = 2005;

int pre[MAX_N][2], suf[MAX_N][2];
int g[MAX_N][MAX_N][2][2];
int w[MAX_N], N;

int main() {
	scanf("%d", &N);
	rep (i, 0, N) { scanf("%d", &w[i]); w[i]--; }
	rep (i, 0, N) {
		if (i) memcpy(pre[i], pre[i - 1], sizeof pre[i]);
		down (j, 2, w[i]) upmax(pre[i][j], pre[i][w[i]] + 1);
	}
	down (i, N, 0) {
		if (i < N - 1) memcpy(suf[i], suf[i + 1], sizeof suf[i]);
		rep (j, 0, w[i] + 1) upmax(suf[i][j], suf[i][w[i]] + 1);
	}
	int ans = pre[N - 1][1];
	rep (i, 0, N) {
		rep (a, 0, w[i] + 1) rep (b, w[i], 2) {
			g[i][i][a][b] = 1;
		}
	}
	rep (l, 1, N) rep (i, 0, N - l) {
		int j = i + l;
		rep (l, 0, 2) rep (a, 0, 2 - l) {
			int b = a + l;
			g[i][j][a][b] = max((a < 1 ? g[i][j][a + 1][b] : 0), (b ? g[i][j][a][b - 1] : 0));
			upmax(g[i][j][a][b], g[i + 1][j][a][b] + (b == w[i]));
			upmax(g[i][j][a][b], g[i][j - 1][a][b] + (a == w[j]));
			upmax(ans, (i ? pre[i - 1][a] : 0) + g[i][j][a][b] + (j < N - 1 ? suf[j + 1][b] : 0));
		}
	}
	printf("%d\n", ans);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
long long p;
int k;
int cnt=0;
int ans[107];
int get()
{
	int x=p%k;
	if (x<0) x+=k;
	return x%k;
}
int main()
{
	scanf("%lld%d",&p,&k);
	while (p!=0)
	{
		++cnt;
		ans[cnt]=get();
		p-=get();
		p/=(-k);
	}
	printf("%d\n",cnt);
	for (int i=1;i<=cnt;i++)
		printf("%d ",ans[i]);
	printf("\n");
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

typedef long double db;
const db eps=1e-12;

struct Point
{
    db x,y;
    Point(){}
    Point(db _x,db _y):x(_x),y(_y){}
    Point operator + (const Point &t)const
    {
        return Point(x+t.x,y+t.y);
    }
    Point operator - (const Point &t)const
    {
        return Point(x-t.x,y-t.y);
    }
    Point operator * (const db &t)const
    {
        return Point(x*t,y*t);
    }
    Point operator / (const db &t)const
    {
        return Point(x/t,y/t);
    }
    bool operator < (const Point &t)const
    {
        return fabs(x-t.x)<eps ? y<t.y : x<t.x;
    }
    bool operator == (const Point &t)const
    {
        return fabs(x-t.x)<eps && fabs(y-t.y)<eps;
    }
    db len()const
    {
        return sqrt(x*x+y*y);
    }
    Point rot90()const
    {
        return Point(-y,x);
    }
};

struct Circle
{
    Point o;
    db r;
    Circle(){}
    Circle(Point _o,db _r):o(_o),r(_r){}
    friend vector<Point> operator & (const Circle &c1,const Circle &c2)
    {
        db d=(c1.o-c2.o).len();
        if(d>c1.r+c2.r+eps || d<fabs(c1.r-c2.r)-eps)
            return vector<Point>();
        db dt=(c1.r*c1.r-c2.r*c2.r)/d,d1=(d+dt)/2;
        Point dir=(c2.o-c1.o)/d,pcrs=c1.o+dir*d1;
        dt=sqrt(max(0.0L,c1.r*c1.r-d1*d1)),dir=dir.rot90();
        return vector<Point>{pcrs+dir*dt,pcrs-dir*dt};
    }
}p[5];

struct DSU
{
    int fa[5];
    void init(int n)
    {
        for(int i=1;i<=n;i++)
            fa[i]=i;
    }
    int find(int x)
    {
        return fa[x]==x ? x : fa[x]=find(fa[x]);
    }
    void merge(int x,int y)
    {
        x=find(x),y=find(y);
        if(x!=y)fa[x]=y;
    }
}dsu;

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        cin>>p[i].o.x>>p[i].o.y>>p[i].r;
    vector<Point> all;
    dsu.init(n);
    int e=0;
    for(int i=1;i<=n;i++)
    {
        vector<Point> pat;
        for(int j=1;j<=n;j++)if(i!=j)
        {
            vector<Point> tmp=p[i]&p[j];
            if(!tmp.empty())dsu.merge(i,j);
            for(int k=0;k<(int)tmp.size();k++)
                all.push_back(tmp[k]),pat.push_back(tmp[k]);
        }
        sort(pat.begin(),pat.end());
        e+=unique(pat.begin(),pat.end())-pat.begin();
    }
    sort(all.begin(),all.end());
    int v=unique(all.begin(),all.end())-all.begin(),c=0;
    for(int i=1;i<=n;i++)
        c+=(dsu.find(i)==i);
    cout<<e-v+c+1<<endl;
    return 0;
}

#include <cmath>
#include <cstdio>
#include <algorithm>

static const int MAXN = 3;
static const double EPS = 1e-9;

static int n;
static int x[MAXN], y[MAXN], r[MAXN];

// -2: internally separate
// -1: internally tangent
//  0: intersecting
// +1: externally tangent
// +2: externally separate
static int g[MAXN][MAXN];
// Number of points passed by all three circles
static int conc;

inline int rel(int a, int b)
{
    int dssq = (x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]),
        dfsq = (r[a] - r[b]) * (r[a] - r[b]),
        smsq = (r[a] + r[b]) * (r[a] + r[b]);

    if (dssq < dfsq) return -2;
    else if (dssq == dfsq) return -1;
    else if (dssq < smsq) return 0;
    else if (dssq == smsq) return +1;
    else return +2;
}

inline void get_intersections(int a, int b, double ix[2], double iy[2])
{
    double angle = atan2(y[b] - y[a], x[b] - x[a]);
    double ds = sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b]));
    double delta = acos((ds * ds + r[a] * r[a] - r[b] * r[b]) / (2.0 * r[a] * ds));
    ix[0] = x[a] + r[a] * cos(angle + delta);
    iy[0] = y[a] + r[a] * sin(angle + delta);
    ix[1] = x[a] + r[a] * cos(angle - delta);
    iy[1] = y[a] + r[a] * sin(angle - delta);
}

inline bool on_circle(int a, double x0, double y0)
{
    return fabs((x[a] - x0) * (x[a] - x0) + (y[a] - y0) * (y[a] - y0) - r[a] * r[a]) <= EPS;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d%d%d", &x[i], &y[i], &r[i]);

    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j)
            g[i][j] = g[j][i] = rel(i, j);

    conc = 0;
    if (n == 3) {
        for (int i = 0; i < 2; ++i) {
            for (int j = i + 1; j < 3; ++j) if (g[i][j] >= -1 && g[i][j] <= +1) {
                int k = 3 - i - j;
                double ix[2], iy[2];
                get_intersections(i, j, ix, iy);
                if (on_circle(k, ix[0], iy[0])) ++conc;
                if (on_circle(k, ix[1], iy[1]) && g[i][j] == 0) ++conc;
                break;
            }
            if (conc != 0) break;
        }
    }

    if (n == 1) {
        puts("2");
    } else if (n == 2) {
        puts(g[0][1] == 0 ? "4" : "3");
    } else if (n == 3) {
        int x[3] = { g[0][1], g[0][2], g[1][2] };
        std::sort(x, x + 3);
        if (x[0] == -2) {
            printf("%d\n", 4 + (x[1] == 0) + (x[2] == 0));
        } else if (x[0] == -1) {
            if (x[1] == -1) {
                printf("%d\n", x[2] == -1 ? 4 : (6 - x[2]));
            } else {
                switch (x[1] * 10 + x[2]) {
                    case 00: printf("%d\n", 7 - conc); break;
                    case 01: puts("6"); break;
                    case 02: puts("5"); break;
                    case 11: case 12: case 22: puts("4"); break;
                    default: puts("> <");
                }
            }
        } else if (x[0] >= +1) {
            puts(x[0] == +1 && x[2] == +1 ? "5" : "4");
        } else {    // x[0] == 0
            switch (x[1] * 10 + x[2]) {
                case 00: printf("%d\n", 8 - conc); break;
                case 01: printf("%d\n", 7 - conc); break;
                case 02: puts("6"); break;
                case 11: puts("6"); break;
                case 12: puts("5"); break;
                case 22: puts("5"); break;
                default: puts("> <");
            }
        }
    } else puts("> <");

    return 0;
}

#include <bits/stdc++.h>
typedef long long LL;
const int mod = (int)1e9 + 7, inv2 = (mod + 1) / 2, inv3 = (mod + 1) / 3, inv5 = (mod * 2 + 1) / 5, inv7 = (mod + 1) / 7;
const int inv6 = (LL)inv2 * inv3 % mod, inv30 = (LL)inv5 * inv6 % mod, inv42 = (LL)inv6 * inv7 % mod;
const int coeff[4][8] = {
{0, 1}, // sum(b^0) = n
{0, inv6, inv2, inv3}, // sum(b^2) = 1/6 n + 1/2 n^2 + 1/3 n^3
{0, mod - inv30, 0, inv3, inv2, inv5}, // sum(b^4) = -1/30 n + 1/3 n^3 + 1/2 n^4 + 1/5 n^5
{0, inv42, 0, mod - inv6, 0, inv2, inv2, inv7} // sum(b^6) = 1/42 n - 1/6 n^3 + 1/2 n^5 + 1/2 n^6 + 1/7 n^7
};
LL n;
int f[4], g[4], ans;
int main() {
	scanf("%lld", &n);
	int nn = n % mod;
	f[0] = nn * (nn + 1LL) % mod * (nn + 2) % mod;
	f[1] = (3LL * nn + 4) % mod;
	f[2] = mod - 3LL * (nn + 2) % mod;
	f[3] = 2;
	for(int x = 0; (LL)x * x <= n; ++x) {
		LL rem = n - (LL)x * x;
		int yLim = (int)ceil(sqrtl(rem));
		for( ; (LL)yLim * yLim <= rem; ++yLim);
		for( ; (LL)yLim * yLim > rem; --yLim);
		int sum = 0, x2 = (LL)x * x % mod, x4 = (LL)x2 * x2 % mod, x6 = (LL)x2 * x4 % mod;
		g[0] = (f[0] + (LL)f[1] * x2 + (LL)f[2] * x4 + (LL)f[3] * x6) % mod;
		g[1] = (f[1] + 2LL * f[2] * x2 + 3LL * f[3] * x4) % mod;
		g[2] = (f[2] + 3LL * f[3] * x2) % mod;
		g[3] = f[3];
		for(int i = 0; i < 4; ++i) {
			int tmp = 0;
			for(int j = i << 1 | 1; j >= 0; --j)
				tmp = ((LL)tmp * yLim + coeff[i][j]) % mod;
			sum = (sum + (LL)g[i] * (tmp << 1 | !i)) % mod;
		}
		x && (sum <<= 1) >= mod && (sum -= mod);
		(ans += sum) >= mod && (ans -= mod);
	}
	ans = (LL)ans * inv6 % mod;
	printf("%d\n", ans);
	return 0;
}

#include <bits/stdc++.h>


using namespace std;

#define re return
#define sz(a) (int)a.size()
#define mp(a, b) make_pair(a, b)
#define fi first
#define se second
#define re return
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define bend(a) a.begin(),a.end()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef long double ld;
typedef unsigned long long ull;
const ll mod = int(1e9) + 7;

ll n, sum1, sum2, sum3, sum4, ans;
vector<ll> cp;

ll mdd(ll c) {
	c %= mod;
	if (c < 0) c += mod;
	re c;
}

ll pow1(ll k, ll st) {
	ll ans = 1;
	while (st) {
		if (st & 1) ans = mdd(ans * k);
		k = mdd(k * k);
		st >>= 1;
	}
	re ans;
}

ll get_sum(ll n) {
	n %= mod;
	n += mod;
	n %= mod;
	re (n * (n + 1) / 2LL) % mod;
}

ll get_cnt(ll a) {
	a = mdd(a);
	re mdd(mdd(2LL * mdd(a * a) * a) - mdd(3LL * mdd(a * a) * mdd(n + 2)) + mdd(mdd(a) * mdd(3LL * n + 4)) + mdd(n) * mdd(mdd(mdd(n) * mdd(n)) + 3LL * n + 2LL));
}

int main() {
	iostream::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (ll k = 1; k * k <= n; k++) {
		ll c = mdd(k * k);
		cp.push_back(k * k);
		sum1 = mdd(sum1 + c);
		sum2 = mdd(sum2 + mdd(c * c));
		sum3 = mdd(sum3 + mdd(mdd(c * c) * c));
		sum4 = mdd(sum4 + get_cnt(c));
		//cout << sum4 << "\n";
	}
	ans = mdd(get_cnt(1) + 4LL * sum4);
	ll k1 = 2, k2 = mdd(-3LL * (n + 2)), k3 = mdd(3LL * n + 4);
	for (ll a = 0; ; a++){
		while (sz(cp) && cp.back() + (a+1LL) * (a + 1LL) > n) {
			ll c = mdd(cp.back() + a * a);
			sum1 = mdd(sum1 - c);
			sum2 = mdd(sum2 - mdd(c * c));
			sum3 = mdd(sum3 - mdd(mdd(c * c) * c));
			sum4 = mdd(sum4 - mdd(get_cnt(c)));
			cp.pop_back();
			continue;
		}		
		if (sz(cp) == 0) break;
		ll k = mdd(2LL * a + 1), ksq = mdd(k * k), ktr = mdd(ksq * k);
		//cout << sum4 << "\n";
		sum4 = mdd(sum4 + mdd(ll(sz(cp)) * mdd(k1 * ktr + k2 * ksq + k3 * k)) +
			   mdd(sum1 * mdd(2LL * k * k2 + 3LL * k1 * ksq)) +
			   mdd(sum2 * mdd(3LL * k * k1)));
		//cout << sum4 << "\n";
		ans = mdd(ans + 4LL * sum4);
		sum3 = mdd(sum3 + mdd(ll(sz(cp)) * ktr) + mdd(sum2 * 3LL * k) + mdd(ksq * 3LL * sum1));
		sum2 = mdd(sum2 + mdd(ll(sz(cp)) * ksq) + mdd(2LL * sum1 * k));
		sum1 = mdd(sum1 + mdd(ll(sz(cp)) * k));
		//cout << sum3 << " " << sum2 << " " << sum1 << "\n";
	}
	//cout << ans /6<< "\n";
	ans = mdd(ans * pow1(6, mod - 2));
	cout << ans;
} 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = (int)3e5 + 3;
int n, a[maxn], cnt, p[maxn], m, out[maxn];
LL f[maxn];
bool v[maxn];
int descension(int pos) {
	int dt = min(a[pos], a[pos + 1]);
	if(dt)
		out[++m] = pos;
	a[pos] -= dt;
	a[pos + 1] -= dt;
	return dt;
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		LL odd = f[max(i - 2, 0)] + a[i], even = f[max(i - 3, 0)] + max(a[i - 1], a[i]);
		f[i] = min(odd, even);
		v[i] = f[i] != odd;
	}
	// a[n + 1] = 0;
	LL ans = min(f[n - 1], f[n]);
	// printf("%lld\n", ans);
	for(int i = n - (ans == f[n - 1]); i > 0; i -= 2 + v[i])
		p[++cnt] = i;
	reverse(p + 1, p + cnt + 1);
	for(int i = 1; i <= cnt; ++i) {
		int pre = p[i - 1], cur = p[i], ctr = 0;
		if(v[cur])
			ctr += descension(cur - 1);
		ctr += descension(pre + 1);
		ctr += descension(cur);
		assert(ctr == f[cur] - f[pre]);
	}
	printf("%d\n", m);
	for(int i = 1; i <= m; ++i)
		printf("%d\n", out[i]);
	return 0;
}

First approach: Optimize the straightforward solution.

Multiply instead of divide. What happens to the last digit when multiplying?

Consider islands of two colours and the bridges between them.

Iterate over all possible combination, order and direction of extra edges.

First approach: 2D segment tree (or quadtree) with a set or vector on each node, representing the set of barriers that cover this node.

#include <bits/stdc++.h>
using namespace std;
#define Maxn 4000007
bool vis[Maxn];
int a[4007],b[4007],n;
int main()
{
	scanf("%d",&n);
	memset(vis,false,sizeof(vis));
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		vis[a[i]]=true;
	}
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		vis[b[i]]=true;
	}
	int ans=0;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			if (vis[a[i]^b[j]]) ++ans;
	if (ans%2==0) printf("Karen\n"); else printf("Koyomi\n");
	return 0;
}

#include <stdio.h>

int main()
{
    puts("Karen");
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
long long L,R;
int ans;
int main()
{
	scanf("%lld%lld",&L,&R);
	if (R-L>=10) printf("%d\n",0);
	else
	{
		ans=1;
		for (long long i=L+1;i<=R;i++)
			ans=(1LL*ans*(i%10))%10;
		printf("%d\n",ans);
	}
	return 0;
}

#include <bits/stdc++.h>
#define Maxn 5007
#define modp 998244353
int p[Maxn][Maxn];
int pre[Maxn];
int a,b,c;
int solve(int x,int y)
{
	int res=0;
	for (int k=0;k<=x&&k<=y;k++)
	{
		int del=pre[k];
		del=(1LL*del*p[x][k])%modp;
		del=(1LL*del*p[y][k])%modp;
		res=(res+del)%modp;
	}
	return res;
}
int main()
{
	scanf("%d%d%d",&a,&b,&c);
	memset(p,0,sizeof(p));
	p[0][0]=1;
	for (int i=1;i<=5000;i++)
	{
		p[i][0]=1;
		for (int j=1;j<=i;j++)
			p[i][j]=(p[i-1][j-1]+p[i-1][j])%modp;
	}
	memset(pre,0,sizeof(pre));
	pre[0]=1;
	for (int i=1;i<=5000;i++)
		pre[i]=(1LL*pre[i-1]*i)%modp;
	int ans=1;
	ans=(1LL*ans*solve(a,b))%modp;
	ans=(1LL*ans*solve(b,c))%modp;
	ans=(1LL*ans*solve(a,c))%modp;
	printf("%d\n",ans);
	return 0;
}

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>

using namespace std;

const int MAXN=255;

const int Mod=1000000007;
inline void add_mod(int &x,int y)
{
    x=(x+y<Mod ? x+y : x+y-Mod);
}

int u[MAXN],v[MAXN];

map<int,int> mp;
inline int get_id(int x)
{
    if(!mp[x])mp[x]=(int)mp.size();
    return mp[x];
}

vector<int> e[MAXN];
void add_edge(int u,int v)
{
    e[u].push_back(v);
    e[v].push_back(u);
}

inline int cal_size(int u,int n,int d)
{
    int t=u,c=0,res;
    while(t)c++,t>>=1;
    res=(1<<(d-c+1))-1,t=c;
    while(t<d)t++,u=u<<1|1;
    return res-max(min(u-n,1<<(d-c)),0);
}

int num[MAXN];
void pre_dp(int u,int f)
{
    for(auto &v:e[u])
    {
        if(v==f)continue;
        num[u]-=num[v];
        pre_dp(v,u);
    }
}

int vis[MAXN];
void dfs(int u,int &tot)
{
    add_mod(tot,num[u]);
    vis[u]=1;
    for(auto &v:e[u])
        if(!vis[v])dfs(v,tot);
    vis[u]=0;
}

int main()
{
    int n,m,d=0;
    scanf("%d%d",&n,&m);
    while((1<<d)<=n)d++;
    get_id(1);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&u[i],&v[i]);
        int t=u[i];
        while(t)get_id(t),t>>=1;
        t=v[i];
        while(t)get_id(t),t>>=1;
    }
    for(auto &t:mp)
    {
        int u=t.first,id=t.second;
        if(u>1)add_edge(get_id(u),get_id(u>>1));
        num[id]=cal_size(u,n,d);
    }
    pre_dp(1,0);
    for(int i=0;i<m;i++)
        add_edge(get_id(u[i]),get_id(v[i]));
    int res=0;
    for(int i=1;i<=(int)mp.size();i++)
    {
        int tot=0;
        dfs(i,tot);
        add_mod(res,1LL*tot*num[i]%Mod);
    }
    printf("%d\n",res);
    return 0;
}

#include <bits/stdc++.h>

#define rep(i, x, y) for (int i = (x), _ = (y); i <= _; ++i)
#define down(i, x, y) for (int i = (x) - 1, _ = (y); i >= _; --i)
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define bin(x) (1<<(x))
//#define LX_JUDGE

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

template<typename T> inline void upmax(T &x, T y) { x < y ? x = y : 0; }
template<typename T> inline void upmin(T &x, T y) { x > y ? x = y : 0; }

template<typename T> inline void read(T &x) {
	char c;
	while ((c = getchar()) < '0' or c > '9');
	for (x = c - '0'; (c = getchar()) >= '0' and c <= '9'; x = x * 10 + c - '0');
}

const int inf = 0x3f3f3f3f;
const int MAX_N = 2500;

struct Data {
	int u, d, id;
	Data() {}
	Data(int u, int d, int id) : u(u), d(d), id(id) {}
};

class SegmentTree {
	map<pii, int> G;
	int n, pcnt;
	vector<Data> H[MAX_N * 4 + 255];
#define ls (o << 1)
#define rs (o << 1 | 1)

	int _l, _r, _u, _d, _id;

	void ins(int o, int l, int r) {
		if (_l <= l and r <= _r) {
			//printf("%d %d %d %d\n", l, r, _u, _d);
			H[o].pb(Data(_u, _d, _id));
			return ;
		}
		int m = (l + r) / 2;
		if (_l <= m) ins(ls, l, m);
		if (m < _r) ins(rs, m + 1, r);
	}
	void del(int o, int l, int r) {
		if (_l <= l and r <= _r) {
			for (vector<Data>::iterator it = H[o].begin(); it != H[o].end(); it++) {
				if (it->id == _id) {
					H[o].erase(it);
					break ;
				}
			}
			return ;
		}
		int m = (l + r) / 2;
		if (_l <= m) del(ls, l, m);
		if (m < _r) del(rs, m + 1, r);
	}
	inline int _ask(const vector<Data> &q, int h) {
		int best = inf, ans = -1;
		for (auto to : q) {
			if (to.u <= h and h <= to.d and to.d - to.u < best) {
				best = to.d - to.u;
				ans = to.id;
			}
		}
		return ans;
	}
	int ask(int o, int l, int r) {
		if (l == r) return _ask(H[o], _u);
		int m = (l + r) / 2;
		int ans = m >= _l ? ask(ls, l, m) : ask(rs, m + 1, r);
		return ans < 0 ? _ask(H[o], _u) : ans;
	}
#undef ls
#undef rs
public :
	void init(int n) {
		this->n = n;
		pcnt = 1;
	}
	void ins(int l, int u, int r, int d) {
		G[mp(l, u)] = _id = pcnt++;
		_l = l, _r = r, _u = u, _d = d;
		ins(1, 1, n);
	}
	void del(int l, int u, int r, int d) {
		_id = G[mp(l, u)];
		G.erase(mp(l, u));
		_l = l, _r = r;
		del(1, 1, n);
	}
	int ask(int x, int y) {
		_l = x, _u = y;
		return ask(1, 1, n);
	}
} my;

int main() {
	int n, m, Q;
	read(n), read(m), read(Q);
	my.init(2500); // FIX ME
	int opt, r1, c1, r2, c2;
	while (Q--) {
		read(opt), read(r1), read(c1), read(r2), read(c2);
		if (opt == 3) {
			//int a = my.ask(r1, c1), b = my.ask(r2, c2);
			//printf("%d %d\n", a, b);
			puts(my.ask(r1, c1) == my.ask(r2, c2) ? "Yes" : "No");
		} else if (opt == 1) {
			my.ins(r1, c1, r2, c2);
		} else {
			my.del(r1, c1, r2, c2);
		}
	}
	return 0;
}

#include <bits/stdc++.h>
#define Maxn 2507
using namespace std;
int n,m,q;
map<pair<pair<int,int>,pair<int,int> >,pair<unsigned long long,unsigned long long> > mp;
pair<unsigned long long,unsigned long long> s[Maxn][Maxn];
void add(int x,int y,pair<unsigned long long,unsigned long long> del)
{
	for (int kx=x;kx<=2503;kx+=kx&(-kx))
		for (int ky=y;ky<=2503;ky+=ky&(-ky))
		{
			s[kx][ky].first+=del.first;
			s[kx][ky].second+=del.second;
		}
}
pair<unsigned long long,unsigned long long> query(int x,int y)
{
	pair<unsigned long long,unsigned long long> res=make_pair(0,0);
	for (int kx=x;kx;kx-=kx&(-kx))
		for (int ky=y;ky;ky-=ky&(-ky))
		{
			res.first+=s[kx][ky].first;
			res.second+=s[kx][ky].second;
		}
	return res;
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	memset(s,0,sizeof(s));
	srand(20001206);
	mp.clear();
	for (int i=1;i<=q;i++)
	{
		int t,r1,c1,r2,c2;
		scanf("%d%d%d%d%d",&t,&r1,&c1,&r2,&c2);
		pair<unsigned long long,unsigned long long> del,udel;
		if (t==1)
		{
			del.first=rand();
			del.second=rand();
			udel=make_pair(-del.first,-del.second);
			mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))]=del;
			add(r1,c1,del);
			add(r1,c2+1,udel);
			add(r2+1,c1,udel);
			add(r2+1,c2+1,del);
		} else if (t==2)
		{
			del=mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))];
			mp[make_pair(make_pair(r1,c1),make_pair(r2,c2))]=make_pair(0,0);
			udel=make_pair(-del.first,-del.second);
			add(r1,c1,udel);
			add(r1,c2+1,del);
			add(r2+1,c1,del);
			add(r2+1,c2+1,udel);
		}
		else
		{
			del=query(r1,c1);
			udel=query(r2,c2);
			if (del==udel) printf("Yes\n"); else printf("No\n");
		}
	}
	return 0;
}