### 题解

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<ctype.h>
#include<queue>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define mod 998244353
#define lowbit(x) (x & -x)
#define N 2500005
#define clr(arr) memset(arr, 0, sizeof arr)
#define bset std::bitset<N>
{
x = 0;
Re bool flag = 0;
Re char ch = getchar();
while (!isdigit(ch) && ch != '-') ch = getchar();
if (ch == '-') flag = 1, ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
if (flag) x = -x;
}
struct edge {
int nxt, v, w;
} e[N << 1];
int n, m, k, tot = 1, head[N], cnt;
using namespace std;
inline void addedge (int u, int v, int w)
{
e[++tot] = (edge) {head[u], v, w};
e[++tot] = (edge) {head[v], u, 0};
}
int s, t, que[N], hh, tt, dis[N], cur[N];
inline bool bfs ()
{
memset(dis, 0, sizeof dis);
dis[s] = 1;
que[hh = tt = 1] = s;
while (hh <= tt)
{
int u = que[hh++];
edge (i, u)
if (e[i].w && !dis[v])
{
que[++tt] = v;
dis[v] = dis[u] + 1;
}
}
return dis[t];
}
inline int dfs (int u, int cap)
{
if (u == t) return cap;
Re int used = 0;
for (Re int i = cur[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
if (e[i].w && dis[v] == dis[u] + 1)
{
Re int now = dfs(v, min(cap - used, e[i].w));
if (now)
{
used += now;
e[i].w -= now;
e[i ^ 1].w += now;
if (used == cap) { cur[u] = i; return cap; }
}
}
return used;
}
inline int dinic ()
{
int ret = 0, now;
while (bfs())
{
while (now = dfs(s, inf)) ret += now;
}
return ret;
}
int id[N], l;
int opt, u1, u2, v1, v2, fr, to;
struct segment_tree {
int opt, pos[N];
#define ls (u << 1)
#define rs (u << 1 | 1)
inline void build (int u, int L, int R)
{
if (L == R)
{
pos[u] = id[L];
return;
}
pos[u] = ++cnt;
int mid = L + R >> 1;
build(ls, L, mid); build(rs, mid + 1, R);
}
inline void modify (int u, int L, int R, int l, int r)
{
if (l <= L && R <= r)
{
return;
}
int mid = L + R >> 1;
if (l <= mid) modify(ls, L, mid, l, r);
if (mid < r) modify(rs, mid + 1, R, l, r);
}
} t1, t2;
int main ()
{
scanf("%d %d %d", &n, &m, &k);
cnt = 2;
s = 1; t = 2;
fo (i, 1, k) id[i] = ++cnt;
t1.opt = 1;
t1.build(1, 1, k); t2.build(1, 1, k);
while (m--)
{
if (opt == 1)
{
}
else
if (opt == 2)
{
fr = ++cnt; to = id[v1];
t1.modify(1, 1, k, u1, u2);
}
else
if (opt == 3)
{
fr = id[u1]; to = ++cnt;
t2.modify(1, 1, k, v1, v2);
}
else
if (opt == 4)
{
fr = ++cnt, to = ++cnt;
t1.modify(1, 1, k, u1, u2);
t2.modify(1, 1, k, v1, v2);