#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = 0;  i < (n); ++i)
 
const int n = 1e7;  // limit for array size
int t[2 * n];
 
void build() {  // build the tree
  for (int i = n - 1; i > 0; --i) t[i] = min(t[i<<1], t[i<<1|1]);
}
 
void modify(int p, int value) {  // set value at position p
  for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = min(t[p], t[p^1]);
}
 
int query(int l, int r) {  // sum on interval [l, r)
  int res = INT_MAX;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l&1) res = min(res, t[l++]);
    if (r&1) res = min(res, t[--r]);
  }
  return res;
}
 
int main() {
	rep(i, n) t[i + n] = i;
	build();
	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+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojZGVmaW5lIHJlcChpLCBuKSBmb3IgKGludCBpID0gMDsgIGkgPCAobik7ICsraSkKCmNvbnN0IGludCBuID0gMWU3OyAgLy8gbGltaXQgZm9yIGFycmF5IHNpemUKaW50IHRbMiAqIG5dOwoKdm9pZCBidWlsZCgpIHsgIC8vIGJ1aWxkIHRoZSB0cmVlCiAgZm9yIChpbnQgaSA9IG4gLSAxOyBpID4gMDsgLS1pKSB0W2ldID0gbWluKHRbaTw8MV0sIHRbaTw8MXwxXSk7Cn0KCnZvaWQgbW9kaWZ5KGludCBwLCBpbnQgdmFsdWUpIHsgIC8vIHNldCB2YWx1ZSBhdCBwb3NpdGlvbiBwCiAgZm9yICh0W3AgKz0gbl0gPSB2YWx1ZTsgcCA+IDE7IHAgPj49IDEpIHRbcD4+MV0gPSBtaW4odFtwXSwgdFtwXjFdKTsKfQoKaW50IHF1ZXJ5KGludCBsLCBpbnQgcikgeyAgLy8gc3VtIG9uIGludGVydmFsIFtsLCByKQogIGludCByZXMgPSBJTlRfTUFYOwogIGZvciAobCArPSBuLCByICs9IG47IGwgPCByOyBsID4+PSAxLCByID4+PSAxKSB7CiAgICBpZiAobCYxKSByZXMgPSBtaW4ocmVzLCB0W2wrK10pOwogICAgaWYgKHImMSkgcmVzID0gbWluKHJlcywgdFstLXJdKTsKICB9CiAgcmV0dXJuIHJlczsKfQoKaW50IG1haW4oKSB7CglyZXAoaSwgbikgdFtpICsgbl0gPSBpOwoJYnVpbGQoKTsKCWJvb2wgZiA9IHRydWU7CglyZXAoaSwgbikgewoJCWludCBsID0gcmFuZCgpJW4sIHIgPSByYW5kKCklbjsKCQlpZiAobCA9PSByKSBjb250aW51ZTsKCQlpZiAobCA+IHIpIHN3YXAobCwgcik7CgkJZiAmPSBxdWVyeShsLCByKSA9PSBsOwoJfQoJY291dCA8PCAoZiA/ICJPSyIgOiAiTkciKSA8PCBlbmRsOwp9