There is a grid with $$$n$$$ rows and $$$m$$$ columns, and $$$n \times m$$$ is even. The grid is painted with $$$\frac{n \times m}{2}$$$ kinds of colors. Each kind of color should occupy exactly two adjacent blocks. Two blocks are adjacent means they share an edge in the grid. We define $$$(x,y)$$$ as the block in the $$$x$$$-th row and $$$y$$$-th column.

Little Horse is walking on the grid. Each time he can move to an adjacent block, but he cannot move to the one that shares the same color with his current position. Now, we give you $$$k$$$ conditions. In each condition, we give two positions $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$, and we will tell you whether Little Horse can move from one position to the other one. All you need to do is construct a grid that meets all the conditions.

As we know, for a three-dimensional object, we can draw its three views — front view, top view, and left view. We can regard these views as the projections of the object onto different planes.

For example, consider some blocks like this:

The three views can be drawn as follows:

But Little Rabbit thinks these views are too boring. He wants to observe these blocks in a quite special view — left-front view. Still consider the blocks given above. The left-front view can be drawn as follow:

The left-front view can also be regarded as a projection onto a plane, while the plane is at an angle of $$$45^\circ$$$ to the left view's plane and the front view's plane. The following picture shows how it projects in a top view.

Therefore, if we regard the top view as a grid with $$$n$$$ rows and $$$m$$$ columns, the left-front view should have $$$n+m$$$ columns.

Now, Little Rabbit wants to build some blocks to meet the following conditions:

• The top view is a grid with $$$n$$$ rows and $$$m$$$ columns. Each square should place at least one block.
• Each column of the left-front view has a height of $$$a_1,a_2,\dots,a_{n+m}$$$ from left to right.
• The $$$x_i$$$-th row and the $$$y_i$$$-th column of the top view has exactly $$$h_i$$$ blocks. There are $$$k$$$ such conditions.

Little Rabbit wonders how many different methods there are to meet all the conditions. Since the answer can be very large, please tell him the answer modulo $$$10^9+7$$$.

A Trie is a tree data structure used to store strings. Here is Little Rabbit's C++ code for inserting and querying a string in a Trie. The character set is lowercase letters.

struct Trie {
    int e[N][26], val[N], tot; // N is a constant
    Trie() {
        tot = 0;
        val[0] = Rand(1, 1000000000);
        memset(e, 0, sizeof e);
    }
    void insert(const char *s, int n) { // n is the length of string s
        for (int i = 0, u = 0; i < n; u = e[u][s[i] - 'a'], i++)
            if (!e[u][s[i] - 'a']) {
                e[u][s[i] - 'a'] = ++tot;
                val[tot] = Rand(1, 1000000000);
                // Rand(l, r) can generate
                // distinct random numbers in the range of [l, r]
            }
    }
    int query(const char *s, int n) { // n is the length of string s
        int u = 0;
        for (int i = 0; i < n; u = e[u][s[i] - 'a'], i++)
            if (!e[u][s[i] - 'a'])
                break;
        return val[u];
    }
};

Please note that the integers generated by $$$Rand$$$ function are all distinct.

Little Rabbit inserts some (possibly zero) strings in the Trie by using the $$$insert$$$ function. But after a while, he totally forgets those strings he has inserted. So he uses the $$$query$$$ function $$$n$$$ times to query some strings and gets $$$n$$$ return values. According to these values, you need to tell Little Rabbit how many nodes the Trie has at least. Please note that the root of the Trie should also be counted as a node. In the code above, the number of nodes is $$$\text{tot}+1$$$.

The terrorists have planted some bombs in a building! Our hero, Little Horse, decides to rescue the people in the building. Unfortunately, there is more than one bomb, and Little Horse is unable to defuse all of them. To strive for more time for other people to escape, Little Horse decides to sacrifice himself.

There are $$$n$$$ bombs in the building, each of which has a countdown clock. In the beginning, the $$$i$$$-th bomb's clock is set to $$$a_i$$$. Then:

1. Little Horse chooses one bomb, making its clock increase by $$$1$$$.
2. Every bomb's clock decreases by $$$1$$$.
3. If at least one clock becomes lower than $$$0$$$, all the bombs will explode. Otherwise, go back to step 1.

Obviously, the explosion is not avoidable. What a sad story. But Little Horse doesn't care about his survival now. He just wants to strive for more time. So can you tell him how many times he can do step 1 at most before the explosion?

Little Horse wakes up and finds himself located on a desert island. The only way to escape from the island is by rowing a boat.

There are $$$n$$$ islands numbered from $$$1$$$ to $$$n$$$. Little Horse starts from one of these islands, and he needs to reach the $$$n$$$-th island to be rescued. There are $$$m$$$ waterways, each of which connects two islands. In each waterway, the water flows from one island to the other one. Little Horse will apply the following steps in order:

1. Row the boat. At this step, he can go through at most $$$k$$$ (possibly zero) waterways, either downstream or upstream. Going through each waterway will take $$$1$$$ time unit.
2. Take a rest. At this step, he will randomly choose a waterway downstream and drift through it. He cannot stay at the current island unless there is no such waterway to drift through. Whether he moves or not, taking a rest will take $$$1$$$ time unit.
3. Go back to step 1.

Once Little Horse reaches the $$$n$$$-th island, he will stop immediately. Please tell Little Horse that if he starts from the $$$i$$$-th island, what's the minimum time units he will spend in the worst case.

A monster is attacking our city! Our hero, Little Rabbit, comes to rescue the city. Little Rabbit has a very powerful skill — Fracture Ray. The rays can penetrate the monster and cause huge damage to it. But the monster also has a defensive skill — Hall of Mirrors. Several mirrors will be placed on the battleground, which can reflect the rays. However, since the rays are too powerful, each mirror can only reflect the ray once, and it will break down afterward.

We can regard the battleground as a two-dimensional plane, which can be described by Cartesian coordinates. There are $$$n$$$ double-sided mirrors on the plane, which can be considered as segments that are parallel to the $$$x$$$-axis or $$$y$$$-axis. The coordinates of their endpoints are all integers.

Little Rabbit will emit $$$m$$$ rays. Each ray starts from a point and has an initial direction which is at an angle of $$$45^\circ$$$ to the $$$x$$$-axis and $$$y$$$-axis. When the ray hits a mirror, it will be reflected specularly (the angle of reflection equals the angle of incidence). And it will also break the mirror down, which means the mirror will disappear. Little Rabbit will emit the rays one by one. Only if a ray goes out of range, which means it won't hit any more mirrors, Little Rabbit will emit the next ray. It's guaranteed that the ray won't go through any points whose coordiantes are integers. See the input format for more information.

Little Rabbit has the confidence to defeat the monster. However, he wonders which mirrors the $$$i$$$-th ray will hit.

Little Rabbit and Little Horse love playing odd card games. Now, they are playing a card game called $$$\it{0123-game}$$$.

There are several cards on the table. $$$c_0$$$ of them are labeled with $$$0$$$, $$$c_1$$$ of them are labeled with $$$1$$$, $$$c_2$$$ of them are labeled with $$$2$$$, and $$$c_3$$$ of them are labeled with $$$3$$$. Little Rabbit and Little Horse take turns to play the game, and Little Rabbit goes first. In each turn, the player should choose two cards on the condition that the sum of the numbers on the two cards is no more than $$$3$$$, then replace these two cards with a card labeled with their sum. The player who cannot make a move loses the game.

Little Rabbit and Little Horse wonder who will win the game.

Little Rabbit and Little Horse are playing hide and seek on a plane that can be described by Cartesian coordinates. Little Horse is the hider and Little Rabbit is the seeker. Little Rabbit is eager to win, so he decides to cheat. He prepared three locating devices, placing one at $$$(0,0)$$$, one on Little Horse, and one on himself. These devices cannot show accurate coordinates but can show the Manhattan distance between every two devices.

The Manhattan distance is the sum of the lengths of the projections of the line segment between the points onto the coordinate axes. For example, the Manhattan distance between $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is $$$|x_1-x_2|+|y_1-y_2|$$$. That is to say, if Little Rabbit is at $$$(x_1,y_1)$$$, and Little Horse is at $$$(x_2,y_2)$$$, then Little Rabbit's devices will show $$$d_{01}=|x_1|+|y_1|$$$, $$$d_{02}=|x_2|+|y_2|$$$ and $$$d_{12}=|x_1-x_2|+|y_1-y_2|$$$.

After getting these data, it's much easier for Little Rabbit to find Little Horse. But Little Rabbit wants to know that if their coordinates are integers, how many different situations of their locations there are. Please note that when $$$(x_1,y_1) \neq (x_2,y_2)$$$, Little Rabbit at $$$(x_1,y_1)$$$ and Little Horse at $$$(x_2,y_2)$$$ is a different situation from Little Rabbit at $$$(x_2,y_2)$$$ and Little Horse at $$$(x_1,y_1)$$$. It's also possible that Little Rabbit and Little Horse are at the same point.

Lucid waters and lush mountains are invaluable assets. Guided by this conviction, Little Horse starts to plant trees. Little Horse has $$$n$$$ trees. In the beginning, the $$$i$$$-th tree has a height of $$$h_i$$$. To make the trees grow higher, Little Horse needs to buy fertilizers. The fertilizer which can make a tree's height increase by $$$x$$$ has a cost of $$$x^2+c$$$ ($$$c$$$ is a given const, and $$$x$$$ must be an integer).

Now, Little Horse wants to know what's the minimum cost to make all trees' heights no less than $$$k$$$. There are $$$q$$$ queries about it. Please note that buying only one fertilizer for a tree is not necessarily the best solution. For example, to make a tree's height increse by $$$3$$$, one method is to spend $$$3^2+c$$$, another method is to spend $$$(1^2+c)+(2^2+c)$$$.

Little Horse always does some handcrafts, which is full of joy. This time, he builds a circuit that can turn on and off the bulbs periodically.

There are $$$n$$$ bulbs in the circuit, the $$$i$$$-th of which has a period $$$t_i$$$ and a luminance $$$x_i$$$. Formally, the $$$i$$$-th bulb will be turned on from the $$$(2kt_i+1)$$$-th second to the $$$(2kt_i+t_i)$$$-th second, and it will be turned off from the $$$(2kt_i+t_i+1)$$$-th second to the $$$(2kt_i+2t_i)$$$-th second, $$$k=0,1,2,\dots$$$ When the $$$i$$$-th bulb is on, its luminance will be $$$x_i$$$, otherwise its luminance will be $$$0$$$.

Now, Little Horse wants to know, for each second from the first second to the $$$m$$$-th second, what's the maximum luminance among all the bulbs.

Knowledge is power. Little Rabbit and Little Horse both long for more knowledge, so they always challenge each other to some quizzes. Today, Little Rabbit creates a new quiz for Little Horse.

Little Rabbit gives Little Horse a positive integer $$$x$$$. Little Horse needs to find a set of integers $$$S=\{a_1,a_2,\dots,a_n\}$$$ that meets the following conditions.

• $$$n \ge 2$$$
• $$$a_i \gt 1$$$, for $$$1 \le i \le n$$$
• $$$\sum_{i=1}^na_i=x$$$
• $$$a_i$$$ and $$$a_j$$$ are co-prime, for any $$$i \neq j$$$

For example, if $$$x=12$$$, then $$$S=\{3,4,5\}$$$ and $$$S=\{5,7\}$$$ and $$$S=\{2,3,7\}$$$ are all valid sets. Two integers are said to be co-prime if the only positive integer that evenly divides both of them is $$$1$$$.

We define $$$a_{\max}$$$ as the maximum element of $$$S$$$, and $$$a_{\min}$$$ as the minimum element of $$$S$$$. Little Rabbit wants the value of $$$(a_{\max}-a_{\min})$$$ to be as small as possible. Can you help Little Horse to find the minimum value of $$$(a_{\max}-a_{\min})$$$?

Little Rabbit walks into a shopping mall and comes across a lottery activity. There are $$$n$$$ boxes. Inside the $$$i$$$-th box, there are $$$x_i$$$ balls labeled with $$$2^{a_i}$$$. Little Rabbit can pick out any number (including zero) of balls from each box. The sum of numbers on the chosen balls is the score he gets. Whether Little Rabbit wins a prize in the lottery depends on the score.

However, Little Rabbit doesn't care if he can win a prize. He is curious about how many different scores he is likely to get. Can you help him with it? Since the answer can be very large, please tell him the answer modulo $$$10^9+7$$$.