#include <bits/stdc++.h> // NeOWami
using namespace std;
#define ft first
#define sc second
#define int long long
const int N = 1e5 + 5;
int n, m, k;
vector<vector<int>> pos, bit;
vector<int> posX;
struct query {
int type, l, r, u, v;
};
query Q[N];
inline void fakeUpX(int l) {
// posX push l
}
inline void fakeGetRectX(int l, int u) {
// fakeUpX l
// fakeUpX u
}
inline void compressX() {
posX.push_back(-1);
sort(posX.begin(), posX.end());
posX.erase(unique(posX.begin(), posX.end()), posX.end());
pos.resize(posX.size(), {});
bit.resize(posX.size(), {});
}
inline void fakeUp(int u, int v) {
// pos[i] push v
}
inline void fakeGet(int u, int v) {
// pos[i] push v
}
inline void fakeGetRect(int l, int r, int u, int v) {
fakeGet(u, v);
fakeGet(l - 1, v);
fakeGet(u, r - 1);
fakeGet(l - 1, r - 1);
}
inline void compress() {
for (int i = 1; i < pos.size(); i++) {
pos[i].push_back(-1);
sort(pos[i].begin(), pos[i].end());
pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
bit[i].resize(pos[i].size(), 0);
}
}
inline void update(int u, int v, int t) {
}
inline int get(int u, int v) {
}
int getRect(int l, int r, int u, int v) {
return get(u, v) - get(l - 1, v) - get(u, r - 1) + get(l - 1, r - 1);
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+IC8vIE5lT1dhbWkKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgZnQgZmlyc3QKI2RlZmluZSBzYyBzZWNvbmQKI2RlZmluZSBpbnQgbG9uZyBsb25nCmNvbnN0IGludCBOID0gMWU1ICsgNTsKCmludCBuLCBtLCBrOwp2ZWN0b3I8dmVjdG9yPGludD4+IHBvcywgYml0Owp2ZWN0b3I8aW50PiBwb3NYOwpzdHJ1Y3QgcXVlcnkgewogICAgaW50IHR5cGUsIGwsIHIsIHUsIHY7Cn07CnF1ZXJ5IFFbTl07CgppbmxpbmUgdm9pZCBmYWtlVXBYKGludCBsKSB7CiAgICAvLyBwb3NYIHB1c2ggbAp9CmlubGluZSB2b2lkIGZha2VHZXRSZWN0WChpbnQgbCwgaW50IHUpIHsKICAgIC8vIGZha2VVcFggbAogICAgLy8gZmFrZVVwWCB1Cn0KaW5saW5lIHZvaWQgY29tcHJlc3NYKCkgewogICAgcG9zWC5wdXNoX2JhY2soLTEpOwogICAgc29ydChwb3NYLmJlZ2luKCksIHBvc1guZW5kKCkpOwogICAgcG9zWC5lcmFzZSh1bmlxdWUocG9zWC5iZWdpbigpLCBwb3NYLmVuZCgpKSwgcG9zWC5lbmQoKSk7CiAgICBwb3MucmVzaXplKHBvc1guc2l6ZSgpLCB7fSk7CiAgICBiaXQucmVzaXplKHBvc1guc2l6ZSgpLCB7fSk7Cn0KCmlubGluZSB2b2lkIGZha2VVcChpbnQgdSwgaW50IHYpIHsKICAgIC8vIHBvc1tpXSBwdXNoIHYKfQoKaW5saW5lIHZvaWQgZmFrZUdldChpbnQgdSwgaW50IHYpIHsKICAgIC8vIHBvc1tpXSBwdXNoIHYKfQoKaW5saW5lIHZvaWQgZmFrZUdldFJlY3QoaW50IGwsIGludCByLCBpbnQgdSwgaW50IHYpIHsKICAgIGZha2VHZXQodSwgdik7CiAgICBmYWtlR2V0KGwgLSAxLCB2KTsKICAgIGZha2VHZXQodSwgciAtIDEpOwogICAgZmFrZUdldChsIC0gMSwgciAtIDEpOwp9CgppbmxpbmUgdm9pZCBjb21wcmVzcygpIHsKICAgIGZvciAoaW50IGkgPSAxOyBpIDwgcG9zLnNpemUoKTsgaSsrKSB7CiAgICAgICAgcG9zW2ldLnB1c2hfYmFjaygtMSk7CiAgICAgICAgc29ydChwb3NbaV0uYmVnaW4oKSwgcG9zW2ldLmVuZCgpKTsKICAgICAgICBwb3NbaV0uZXJhc2UodW5pcXVlKHBvc1tpXS5iZWdpbigpLCBwb3NbaV0uZW5kKCkpLCBwb3NbaV0uZW5kKCkpOyAgIAogICAgICAgIGJpdFtpXS5yZXNpemUocG9zW2ldLnNpemUoKSwgMCk7CiAgICB9Cn0KaW5saW5lIHZvaWQgdXBkYXRlKGludCB1LCBpbnQgdiwgaW50IHQpIHsKfQoKaW5saW5lIGludCBnZXQoaW50IHUsIGludCB2KSB7Cn0KaW50IGdldFJlY3QoaW50IGwsIGludCByLCBpbnQgdSwgaW50IHYpIHsKICAgIHJldHVybiBnZXQodSwgdikgLSBnZXQobCAtIDEsIHYpIC0gZ2V0KHUsIHIgLSAxKSArIGdldChsIC0gMSwgciAtIDEpOwp9Cg==