#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
const int n = 1 << 22;
int dat[2 * n];
void init() {
for (int i = n - 1; i > 0; --i) dat[i] = min(dat[2*i], dat[2*i+1]);
}
void update(int k, int a) {
k += n;
dat[k] = a;
while (k > 1) {
k /= 2;
dat[k] = min(dat[2*k], dat[2*k+1]);
}
}
int query(int a, int b, int k = 1, int l = 0, int r = n) {
if (r <= a || b <= l) return INT_MAX;
if (a <= l && r <= b) return dat[k];
else {
int vl = query(a, b, 2*k, l, (l+r)/2);
int vr = query(a, b, 2*k+1, (l+r)/2, r);
return min(vl, vr);
}
}
int main() {
rep(i, n) dat[i + n] = i;
init();
bool f = true;
rep(i, n) {
int l = rand()%n, r = rand()%n;
if (l == r) continue;
if (l > r) swap(l, r);
f &= query(l, r) == l;
}
cout << (f ? "OK" : "NG") << endl;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKI2RlZmluZSByZXAoaSwgbikgZm9yIChpbnQgaSA9IDA7ICBpIDwgKG4pOyArK2kpCiAKY29uc3QgaW50IG4gPSAxIDw8IDIyOwppbnQgZGF0WzIgKiBuXTsKIAp2b2lkIGluaXQoKSB7CiAgZm9yIChpbnQgaSA9IG4gLSAxOyBpID4gMDsgLS1pKSBkYXRbaV0gPSBtaW4oZGF0WzIqaV0sIGRhdFsyKmkrMV0pOwp9CiAKdm9pZCB1cGRhdGUoaW50IGssIGludCBhKSB7CglrICs9IG47CglkYXRba10gPSBhOwoJd2hpbGUgKGsgPiAxKSB7CgkJayAvPSAyOwoJCWRhdFtrXSA9IG1pbihkYXRbMiprXSwgZGF0WzIqaysxXSk7Cgl9IAp9CiAKaW50IHF1ZXJ5KGludCBhLCBpbnQgYiwgaW50IGsgPSAxLCBpbnQgbCA9IDAsIGludCByID0gbikgewoJaWYgKHIgPD0gYSB8fCBiIDw9IGwpIHJldHVybiBJTlRfTUFYOwoJaWYgKGEgPD0gbCAmJiByIDw9IGIpIHJldHVybiBkYXRba107CgllbHNlIHsKCQlpbnQgdmwgPSBxdWVyeShhLCBiLCAyKmssIGwsIChsK3IpLzIpOwoJCWludCB2ciA9IHF1ZXJ5KGEsIGIsIDIqaysxLCAobCtyKS8yLCByKTsKCQlyZXR1cm4gbWluKHZsLCB2cik7Cgl9Cn0KIAppbnQgbWFpbigpIHsKCXJlcChpLCBuKSBkYXRbaSArIG5dID0gaTsKCWluaXQoKTsKCWJvb2wgZiA9IHRydWU7CglyZXAoaSwgbikgewoJCWludCBsID0gcmFuZCgpJW4sIHIgPSByYW5kKCklbjsKCQlpZiAobCA9PSByKSBjb250aW51ZTsKCQlpZiAobCA+IHIpIHN3YXAobCwgcik7CgkJZiAmPSBxdWVyeShsLCByKSA9PSBsOwoJfQoJY291dCA8PCAoZiA/ICJPSyIgOiAiTkciKSA8PCBlbmRsOwp9