Problem 7 / Both heuristics

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Rustam Musin (t.me/musin_acm)
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        Task7 solver = new Task7();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task7 {
        IntIntPair[] a;
        int n;
        int[][] g;
        Query[] queries;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            readInput(in);
            new Solver().solve();
            for (Query q : queries) {
                out.printLine(q.fail ? "fail" : "ok");
            }
        }

        int find(IntIntPair[] a, IntIntPair p) {
            return Arrays.binarySearch(a, p);
        }

        void readInput(InputReader in) {
            n = in.readInt();
            a = new IntIntPair[n];
            for (int i = 0; i < n; i++) {
                a[i] = IntIntPair.makePair(in.readInt(), in.readInt());
            }
            Arrays.sort(a);
            int[] size = new int[n];
            int[] dx = {-1, 0, 1, 0};
            int[] dy = {0, 1, 0, -1};
            for (IntIntPair p : a) {
                int cur = find(a, p);
                for (int d = 0; d < 4; d++) {
                    int x = p.first + dx[d];
                    int y = p.second + dy[d];
                    int id = find(a, IntIntPair.makePair(x, y));
                    if (id >= 0) {
                        size[cur]++;
                    }
                }
            }
            g = new int[n][];
            for (int i = 0; i < n; i++) {
                g[i] = new int[size[i]];
            }
            for (IntIntPair p : a) {
                int cur = find(a, p);
                for (int d = 0; d < 4; d++) {
                    int x = p.first + dx[d];
                    int y = p.second + dy[d];
                    int id = find(a, IntIntPair.makePair(x, y));
                    if (id >= 0) {
                        g[cur][--size[cur]] = id;
                    }
                }
            }
            int queryCount = in.readInt();
            queries = new Query[queryCount];
            for (int i = 0; i < queryCount; i++) {
                int monsterCount = in.readInt();
                int weaponCount = in.readInt();
                int player = find(a, IntIntPair.makePair(in.readInt(), in.readInt()));
                int[] monsters = new int[monsterCount];
                for (int j = 0; j < monsterCount; j++) {
                    monsters[j] = find(a, IntIntPair.makePair(in.readInt(), in.readInt()));
                }
                int[] weapons = new int[weaponCount];
                for (int j = 0; j < weaponCount; j++) {
                    weapons[j] = find(a, IntIntPair.makePair(in.readInt(), in.readInt()));
                }
                queries[i] = new Query(i, player, weapons, monsters);
            }
        }

        class Solver {
            List<Integer>[] tree;
            int treeN;
            boolean[] isActive;
            List<Integer> notRemoved;
            DSU dsu;

            void solve() {
                buildTree();
                dsu = new DSU();
                isActive = new boolean[n];
                notRemoved = new ArrayList<>();
                for (int i = 0; i < n; i++) {
                    notRemoved.add(i);
                }
                dfs(1);
            }

            void buildTree() {
                int log = 1;
                while (1 << log < queries.length) {
                    log++;
                }
                treeN = 1 << log;
                tree = new List[2 * treeN];
                for (int i = 0; i < tree.length; i++) {
                    tree[i] = new ArrayList<>();
                }
                for (int i = 0; i < queries.length; i++) {
                    for (int w : queries[i].weapons) {
                        tree[i + treeN].add(w);
                    }
                }
                for (int i = treeN - 1; i > 0; i--) {
                    List<Integer> both = new ArrayList<>();
                    int leftAt = 0;
                    int rightAt = 0;
                    List<Integer> leftCh = tree[i * 2];
                    List<Integer> rightCh = tree[i * 2 + 1];
                    while (leftAt < leftCh.size() && rightAt < rightCh.size()) {
                        if (leftCh.get(leftAt) == (int) rightCh.get(rightAt)) {
                            both.add(leftCh.get(leftAt));
                            leftAt++;
                            rightAt++;
                        } else if (leftCh.get(leftAt) < rightCh.get(rightAt)) {
                            both.add(leftCh.get(leftAt++));
                        } else {
                            both.add(rightCh.get(rightAt++));
                        }
                    }
                    while (leftAt < leftCh.size()) {
                        both.add(leftCh.get(leftAt++));
                    }
                    while (rightAt < rightCh.size()) {
                        both.add(rightCh.get(rightAt++));
                    }
                    tree[i] = both;
                }
            }

            void dfs(int v) {
                int startActions = dsu.actions.size();
                List<Integer> newNotRemoved = new ArrayList<>();
                List<Integer> removed = new ArrayList<>();
                int at = 0;
                for (int x : notRemoved) {
                    while (at < tree[v].size() && tree[v].get(at) < x) {
                        at++;
                    }
                    if (at < tree[v].size() && tree[v].get(at) == x) {
                        newNotRemoved.add(x);
                    } else {
                        isActive[x] = true;
                        for (int to : g[x]) {
                            if (isActive[to]) {
                                dsu.unite(x, to);
                            }
                        }
                        removed.add(x);
                    }
                }
                if (v < treeN) {
                    List<Integer> old = notRemoved;
                    notRemoved = newNotRemoved;
                    dfs(v * 2);
                    dfs(v * 2 + 1);
                    notRemoved = old;
                } else {
                    if (v - treeN < queries.length) {
                        Query query = queries[v - treeN];
                        for (int monster : query.monsters) {
                            query.fail |= dsu.find(query.player) == dsu.find(monster);
                        }
                    }
                }
                for (int x : removed) {
                    isActive[x] = false;
                }
                dsu.restore(startActions);
            }

        }

        class Query {
            int index;
            int player;
            int[] weapons;
            int[] monsters;
            boolean fail;

            Query(int index, int player, int[] weapons, int[] monsters) {
                this.index = index;
                this.player = player;
                this.weapons = weapons;
                this.monsters = monsters;
                Arrays.sort(weapons);
                Arrays.sort(monsters);
            }

        }

        enum ActionType {
            PARENT,
            RANK,
            ;
        }

        class Action {
            Task7.ActionType type;
            int index;
            int value;

            Action(Task7.ActionType type, int index, int value) {
                this.type = type;
                this.index = index;
                this.value = value;
            }

        }

        class DSU {
            int[] parent;
            int[] rank;
            List<Action> actions = new ArrayList<>();

            DSU() {
                parent = new int[n];
                rank = new int[n];
                for (int i = 0; i < n; i++) {
                    parent[i] = i;
                    rank[i] = 1;
                }
            }

            void saveChange(boolean parent, int index, int value) {
                if (parent) {
                    actions.add(new Action(Task7.ActionType.PARENT, index, value));
                } else {
                    actions.add(new Action(Task7.ActionType.RANK, index, value));
                }
            }

            int find(int v) {
                if (parent[v] == v) {
                    return v;
                }
                saveChange(true, v, parent[v]);
                return parent[v] = find(parent[v]);
            }

            boolean unite(int u, int v) {
                u = find(u);
                v = find(v);
                if (u == v) {
                    return false;
                }
                if (rank[u] > rank[v]) {
                    return unite(v, u);
                }
                saveChange(true, u, parent[u]);
                saveChange(false, v, rank[v]);
                parent[u] = v;
                rank[v] = Math.max(rank[v], rank[u] + 1);
                return true;
            }

            void restore(int leftActions) {
                while (actions.size() > leftActions) {
                    Action action = actions.get(actions.size() - 1);
                    actions.remove(actions.size() - 1);
                    if (action.type == Task7.ActionType.PARENT) {
                        parent[action.index] = action.value;
                    } else {
                        rank[action.index] = action.value;
                    }
                }
            }

        }

    }

    static class IntIntPair implements Comparable<IntIntPair> {
        public final int first;
        public final int second;

        public static IntIntPair makePair(int first, int second) {
            return new IntIntPair(first, second);
        }

        public IntIntPair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }

            IntIntPair pair = (IntIntPair) o;

            return first == pair.first && second == pair.second;
        }

        public int hashCode() {
            int result = first;
            result = 31 * result + second;
            return result;
        }

        public String toString() {
            return "(" + first + "," + second + ")";
        }

        public int compareTo(IntIntPair o) {
            int value = Integer.compare(first, o.first);
            if (value != 0) {
                return value;
            }
            return Integer.compare(second, o.second);
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects) {
            for (int i = 0; i < objects.length; i++) {
                if (i != 0) {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void printLine(Object... objects) {
            print(objects);
            writer.println();
        }

        public void close() {
            writer.close();
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}