As a simple and boring task, you are asked to do modulo on floating numbers.

Given a, b, please calculate .

Notice that the modulo supported by some programming languages like C++, Java or Python might be not enough. You may have to implement a special version for this task.

An array, is called an "Almost Arithmetic Progression" (Almost AP) if you can modify at most 3 elements in the array such that it becomes an arithmetic progression.

Recall the definition of the arithmetic progression: For an array a₁, a₂, ..., a_n to be an AP, a_i + 1 - a_i = c for all 1 ≤ i < n, in which c is a constant (c can be either positive, or negative, or 0).

You are asked to turn an Almost AP into an exact AP by modifying at most 3 numbers.

Functions overriding, is a well-known concept, when we are using inheritance in Object-Oriented Programming (OOP). For those who are not familiar with OOP, I will recall a few things to perhaps refresh your memory.

• A class has at most one parent class. When they do, they are called subclasses inheriting their parents. Subclasses also inherit all the functions declared in their parent classes, and also, all the functions inherited by parents' parents, and so on. Here, we refer to the ancestors as superclasses.
• Subclasses can, of course, declare new functions, and also override the functions already declared in superclasses. This is called overriding.
• When an instance of the subclass calls a function, it will first try to find the code in its own class body, and then its parent, and then its parent's parent, etc., until it reaches the root (the superclass of all classes). If the function has still not been found yet, a runtime error will be raised.

As you might have guessed, we are interested in finding out in which class the function is written when some instance of a particular class calls it.

Given n, k, p, Count the number of non-empty subsets of {0, 1, ..., 2ⁿ - 1} such that the xor-sum of the subset is exactly k. Output the answer modulo p.

You are graduating from your school. There are still some money on your student card, and you don't want to waste even one dollar.

The only way to reset your balance, is to eat lunch, at the school canteen. The canteen offers 2n kinds of meals, selling a₁, a₂, ..., a_2n dollars respectively. Every day, the canteen randomly pick n kinds of meals that will be selling today. In other words, the other half will NOT be on "today's menu". When you recharge your student card, only multiples of 100 is acceptable.

Your balance now is p dollars.

You can always recharge your student card every day. And after the recharging, you will decide to eat at the canteen or not. If yes, you have to pick one of those n kinds of meals. The target is to make the balance on your student card become 0 in 365 days.

The dataset guarantees that this is possible.

You will first read two space-separated integers n and p (1 ≤ n ≤ 500, 1 ≤ p ≤ 100).

The second line contains 2n space-separated integers a₁, a₂, ..., a_2n (1 ≤ a_i ≤ 100). They are the prices of the meals.

Then for every day, you will read n space-separated integers i₁, i₂, ..., i_n from the interactor, denoting which n meals are sold today. The prices are, of course, a_i1, a_i2, ..., a_in. The interactor guarantees that its choices are completely random. There will not be strategies against you.

You will respond in the following way: output two space-separated integers c and s (0 ≤ c ≤ 100, s = 0 or ). c is the number of 100 dollars, that is 100·c dollars you are going to recharging with. s is your choice. If you decide not to eat at the canteen, s = 0.

If when the day is over, your balance is already 0. Please exit your program immediately. Exiting too early or too late will not pass the test.

This seems to be a classic problem in graph theory.

You are given a simple bipartite graph. For each operation you can select a perfect match from the graph and delete it (by deleting all edges in the match). How many times at most can you do such operation?

Specifically, you are given the graph in the following way: we number nodes on the left side 1 to n and nodes on the right side also 1 to n. Edge (i, j) denotes an edge connecting the i-th node on the left side with the j-th node on the right side.

An algorithm, which is obviously ridiculous, adopts the following greedy strategy:

1. Set the answer to be 0.
2. Use Hungarian algorithm to find a perfect match. Return the answer if failed; otherwise increase the answer.
3. Delete the edges in the perfect match, and return to step 2.

You might see that this algorithm sometimes fails to find the optimal solution because at some point, it deletes the "wrong" match when there are multiple options available. However, the perfect match Hungarian will find is closely related to the numbering order of the nodes, at least in our implementation. So, to make it sound more promising, we can adopt a random algorithm that shuffles the node numbers repeatedly, runs the algorithm above and tries to update the answer every time. The algorithm exits when the optimal solution refuses to update in at least 10 recent iterations.

The following is a C++ implementation of this solution. The problem guarantees that we use the checker adopting the same code as provided below.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int maxn = 300;

struct Bipartite {
    // This is just a simple hungarian algorithm.
    int from[maxn], use[maxn], mat[maxn][maxn], n, tot;

    bool match(int x) {
        for (int v = 1; v <= n; ++v)
            if (mat[x][v] && !use[v]) {
                use[v] = 1;
                if (from[v] == -1 || match(from[v])) {
                    from[v] = x;
                    return 1;
                }
            }
        return 0;
    }

    void delete_match() {
        for (int i = 1; i <= n; ++i)
            mat[from[i]][i] = 0;
    }

    int hungary() {
        tot = 0;
        memset(from, -1, sizeof from);
        for (int i = 1; i <= n; ++i) {
            memset(use, 0, sizeof use);
            if (match(i)) ++tot;
        }
        return tot;
    }

    void init(int n) {
        memset(mat, 0, sizeof mat);
        this->n = n;
    }

    void add_edge(int u, int v) {
        mat[u][v] = 1;
    }
} bp;

int solve_bipartite_annealing(int n, vector<P> edges) {
    // Example: solve_bipartite_annealing(3, {{1, 1}, {2, 2}, {3, 2}, {3, 3}});
    int temperature = 10, best = 0;
    int permutation[maxn];
    iota(permutation + 1, permutation + n + 1, 1); // permutation = [1, 2, 3, ...]

    while (temperature > 0) {
        temperature–;
        bp.init(n);
        random_shuffle(permutation + 1, permutation + n + 1);
    		// permutation[1..n] is a random permutation of 1..n

        for (P &e: edges)
            bp.add_edge(e.first, permutation[e.second]);
        int current_ans = 0;
        while (bp.hungary() == n) {  // a perfect match found
            current_ans++;  // increase answer
            bp.delete_match();  // delete matching edges
        }
        if (current_ans > best) {  // a better solution found
            best = current_ans;
            temperature = 10;  // nice, we are motivated!
        }
    }
    return best;
}

Please construct a test case such that this algorithm does not find the optimal under at least 100 random seeds. As this is a classical problem, the jury, of course, know how to solve it correctly. You pass one test when the random algorithm yields a different answer from the correct one under one given random seed.

It's strange that the water temperature in the bathroom is changing during my shower.

Actually, the temperature varies with patterns. The time interval in which I take the shower is [0, z]. Assuming the water temperature initially at time 0 is y, it changes gradually and linearly from y to y + y₁ during the time [0, t₁]; then changes linearly from y + y₁ to y + y₂ during the time [t₁, t₂]; so on and so forth; finally, changes linearly from y + y_n - 1 to y + y_n during the time [t_n - 1, t_n]. Thus, it forms a broken line.

As a human being, I can only do my shower with water temperature between 30 and 30 + h, inclusively. As a lazy human being, I only want to change the water temperature before I start to take the shower. You are asked to find out for how much time at most I can enjoy my shower.

There are two strings s, t, with length infinity. Their periods are n and m, respectively.

Period of a string, has the following definition: if s has a period of n, then s[1..n] = s[n + 1..2n] = s[dn + 1..(d + 1)n] for all d ≥ 0, in which s[i..j] is a substring of s starting from the i-th character and ends with the j-th character.

Now we want to know how many i (1 ≤ i ≤ k) satisfies s_i = t_i. In other words, in how many positions s[1..k] and t[1..k] have the same character?

Count how many ways there are to color a m × n chessboard with black and white, such that the black blocks are 4-connected, and the white blocks are also 4-connected.