import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.io.InputStream;

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

    static class TaskE {
        HashMap<Integer, Integer> map = new HashMap<>();
        boolean[] dp;
        boolean[] vis;
        boxPair[] ans;

        int two(int bit) {
            return 1 << bit;
        }

        boolean contain(int mask, int bit) {
            return ((two(bit) & mask) > 0);
        }

        int get(long val) {
            if (val > Integer.MAX_VALUE || val < Integer.MIN_VALUE) return -1;
            int key = (int) val;
            if (map.containsKey(key) == false) return -1;
            return map.get(key);
        }

        boolean rec(int mask, boolean[] hasCycle) {
            if (hasCycle[mask]) return true;
            if (vis[mask] == true) return dp[mask];
            vis[mask] = true;
            for (int i = mask & (mask - 1); i > 0; i = mask & (i - 1)) {
                if (rec(i, hasCycle) && rec(i ^ mask, hasCycle)) {
                    return dp[mask] = true;
                }
            }
            return dp[mask] = false;
        }

        void findPath(int mask, boolean[] hasCycle, ArrayList<boxPair>[] maskPath) {
            if (hasCycle[mask]) {
                for (boxPair b : maskPath[mask]) {
                    ans[get(b.addTo)] = b;
                }
                return;
            }
            for (int i = mask & (mask -... What is the time complexity of the previous code?