#define _USE_MATH_DEFINES #include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define MT make_tuple #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)<; using vi = vector; using vll = vector; template class DynamicRMQ { int n; Val init; vector dat; Cmp cmp; inline Val query(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return init; if (a <= l && r <= b) return dat[k]; else { Val vl, vr; vl = query(a, b, k << 1, l, (l + r) >> 1); vr = query(a, b, (k << 1) | 1, (l + r) >> 1, r); return cmp(vl, vr) ? vl : vr; } } public: DynamicRMQ() {} DynamicRMQ(int n_, Val init_) :n(1), init(init_) { for (; n(n << 1, init); } void update(int k, Val a) { k += n; dat[k] = a; while (k > 1) { k >>= 1; dat[k] = cmp(dat[k << 1], dat[(k << 1) | 1]) ? dat[k << 1] : dat[(k << 1) | 1]; } } Val query(int a, int b) { return query(a, b, 1, 0, n); } }; typedef DynamicRMQ > RMinQ64; typedef DynamicRMQ > RMaxQ64; typedef DynamicRMQ > RMinQ32; typedef DynamicRMQ > RMaxQ32; vector f(vi a, vi b, vi c) { static const int LIM = 10004; int n = sz(a); vector res(n); RMaxQ32 bma(LIM, -1), cma(LIM, -1); vector> abc(n); rep(i, n)abc[i] = tie(a[i], b[i], c[i], i); sort(all(abc)); reverse(all(abc)); vi id(n); rep(i, n) { tie(a[i], b[i], c[i], id[i]) = abc[i]; } for (int i = 0; i < n;) { int j = i; while (j < n && a[i] == a[j]) { if (bma.query(c[j], LIM) >= b[j] || cma.query(b[j], LIM) >= c[j]) { res[id[j]] = true; } j++; } for (; i < j; ++i) { bma.update(c[i], max(bma.query(c[i], c[i] + 1), b[i])); cma.update(b[i], max(cma.query(b[i], b[i] + 1), c[i])); } } return res; } void solve() { int N; cin >> N; vi P(N), T(N), R(N); rep(i, N) { cin >> P[i] >> T[i] >> R[i]; } auto fp = f(P, T, R); auto ft = f(T, P, R); auto fr = f(R, P, T); rep(i, N) { if (!fp[i] && !ft[i] && !fr[i]) { cout << i + 1 << endl; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15); solve(); return 0; }