// @EXPECTED_RESULTS@: ACCEPTED, COMPILER-ERROR, RUN_TIME_ERROR // Note that the Delft machines do not support all SIMD stuff and crash with signal 4 (SIGILL, illegal instruction). #pragma GCC optimize("Ofast,unroll-loops,fast-math,inline-functions,reorder-functions,omit-frame-pointer,tree-vectorize") #include #pragma GCC target("avx2,avx512f,avx512bw,avx512dq,bmi,bmi2,lzcnt,popcnt") #pragma GCC optimize("section-anchors,ipa-pta,ipa-cp-clone,tree-loop-vectorize,tree-slp-vectorize,align-functions=64,align-loops=64,align-jumps=64") #include "bits/stdc++.h" using namespace std; #define rep(i,a,b) for(int i=(a); i<(b); ++i) #define all(x) x.begin(),x.end() #define sz(x) int(x.size()) typedef vector vi; typedef vector vvi; const int N = 5e4+69; template struct radix_tree{ vector> to = {{}}; vector a = {{}}; inline int link(int i, int x){ int k = sz(to); to[i][x] = k; to.emplace_back(); return k; } T& operator[](int i){ int at = 0; rep(iter,0,2){ int r = i&31, nxt = to[at][r]; at = nxt ? nxt : link(at,r); i/=32; } if (!to[at][i]){ to[at][i] = sz(a); a.emplace_back(); } return a[to[at][i]]; } }; radix_tree mp[N*3][4]; int main(){ cin.tie(NULL),ios::sync_with_stdio(false); int n; cin >> n; vi coords1,coords2; coords1.reserve(N*2+10); coords2.reserve(N*2+10); vvi lists(n); for(auto& v : lists){ int k; cin >> k; v.resize(k); for(auto& x : v) { cin >> x; coords1.push_back(x); } } sort(all(coords1)); coords1.erase(unique(all(coords1)),end(coords1)); for(auto& v : lists) for(auto& x : v) x = lower_bound(all(coords1),x)-begin(coords1); /* preprocessing to remove super small nodes */ { vi cnt(sz(coords1)); for(auto& v : lists) for(auto& x : v) cnt[x]++; for(auto& v : lists){ vi nxt; nxt.reserve(sz(v)); for(auto x : v) if (cnt[x] >= 2) { nxt.push_back(x); coords2.push_back(x); } v = nxt; } sort(all(coords2)); coords2.erase(unique(all(coords2)),end(coords2)); for(auto& v : lists) for(auto& x : v) x = lower_bound(all(coords2),x)-begin(coords2); } /* build graph */ int m = sz(coords2); const int B = cbrt((n+m)/2); vvi adj(n + m), large(n+m), supl(n+m); rep(i,0,n){ for(auto to : lists[i]) { adj[n+to].push_back(i); adj[i].push_back(n+to); } }rep(i,0,n+m) if (sz(adj[i]) >= B) for(auto j : adj[i]) if (sz(adj[j]) >= B) large[i].push_back(j); // run algo auto print = [&](array ans) -> void { sort(all(ans)); cout << coords1[coords2[ans[2]-n]] << ' '; cout << coords1[coords2[ans[3]-n]] << ' '; cout << ans[0]+1 << ' ' << ans[1]+1 << '\n'; exit(0); }; auto add = [&](int u, int v, int mid) -> void { auto& cur = mp[u][v&3][v/4]; if (cur > 0 and cur != mid+1){ // we found sol! array ans = {u,v,mid,cur-1}; print(ans); } cur = mid+1; }; rep(i,0,n+m) { sort(all(adj[i])); const int ss = sz(adj[i]); if (ss < B) { // small cent rep(u,0,ss) rep(v,u+1,ss) add(adj[i][u],adj[i][v],i); }else{ // large trip int st = sz(large[i]); rep(u,0,st) rep(v,u+1,st) add(large[i][u],large[i][v],i); } } // SLL ears rep(i,0,n+m) if (sz(adj[i]) < B) for(auto mid : adj[i]) if (sz(adj[mid]) >= B) for(auto j : large[mid]) add(min(i,j),max(i,j),mid); cout << "impossible\n"; }