The Sticker Album of the ICPC 2020 Nlogonian Subregional just came out! Competitive programming hooligans all over the country are buying albums and collecting stickers, to celebrate the competition.

This sticker album is special because all stickers are equal: a picture of this year's trophy. To complete the album, you just need to collect enough stickers to fill all the slots in it.

You may be asking yourself: where is the fun in collecting those stickers? Well, to make things interesting, the stickers are sold in packets, each with a random number of stickers! Fans celebrate when they find a high number of stickers in a packet, make fun of those who got unlucky and found low numbers of stickers, and brag about filling their whole albums with just a few packets.

You just acquired your own album, and want to start filling it! But before buying your first sticker packets, you wondered: on average, how many packets does one need to buy in order to fill an album?

Battleship is a classic strategy game for two players. Each player places his set of ships in a $$$10 \times 10$$$ grid and then games consist of guessing positions of ships. The actual game rules are not important for this problem, and many variations exist, but here we are interested on a much more basic problem. Given the lists of ships and their positions, your task is to check whether the initial positioning is valid.

The grid rows and columns are numbered from $$$1$$$ to $$$10$$$, and ships are positioned horizontally or vertically, occupying a contiguous sequence of squares of the board. For this problem, a positioning is valid if

• No position is occupied by more than one ship;
• All the ships are totally contained inside the board.

Pepito is an ICPC coach who very often gets to "concat" the names of two existing teams, such as "AJI" and "Oxidados", in order to produce names for new teams, such as "AJIOxidados".

Since Pepito coaches teams from two different universities where he teaches, he had an idea: he will consider all possible such concatenations of a team name from university $$$A$$$, with a team name from university $$$B$$$ (always in that order: first the one from university $$$A$$$, then the one from university $$$B$$$).

So, if team names from university $$$A$$$ are "Buen" and "Kilo", and team names from university $$$B$$$ are "Pan" and "Flauta", all the possible concatenations that he considers are the strings "BuenPan", "BuenFlauta", "KiloPan" and "KiloFlauta".

Furthermore, he calls a certain team peculiar if removal of that team makes the set of concatenations lose all the concatenations that used the name of that team.

In effect, in the previous example all the teams are peculiar. If however we consider names from $$$A$$$ to be "xx" and "xxy" and names from $$$B$$$ to be "z", "yz" and "xx", then "xx" from university $$$A$$$ is not peculiar, because the name "xx" + "yz" = "xxyz" = "xxy" + "z" and can thus be formed without the need to use "xx" from $$$A$$$. For the same reason, "yz", "xxy" and "z" are not peculiar names. The only peculiar name in this case is "xx" from university $$$B$$$, because it is involved in creating the names "xxxx" and "xxyxx", and it is completely impossible to create any of these without using "xx" from university $$$B$$$.

Given the team names from both universities, your task is to calculate how many peculiar teams are there in each university.

In the country of Nlogonia, the citizens perform a special dance to worship the God of divisibility. The dance is performed by $$$N$$$ men and $$$N$$$ women arranged in two concentric circles. The men position themselves on the inner circle, and the women on the outer circle. Every women starts out in front of some man.

The dance consists of $$$K$$$ steps; the first step is taken by the men, the second by the women and so on. At the $$$i$$$-th step, the people whose turn it is rotate $$$P_i$$$ positions in the clockwise direction, while the people in the other circle stay put. In this way, each person changes partner to someone $$$P_i$$$ positions away. A step is valid if every person's partner is different before and after the step AND if no pair of people ever face each other at two different moments in the process.

As part of the ritual, the dance must finish by forming pairs whose sum of ages leave the same remainder when divided by the sacred number $$$M$$$. In other words, if the sum of the ages of one couple (at the end of the dance) leaves remainder $$$R$$$ when divided by $$$M$$$, then every couple has to have sum of ages leaving remainder $$$R$$$ when divided by $$$M$$$.

Given $$$N$$$, $$$M$$$, $$$K$$$ and all of the dancers' ages, figure out in how many ways the dance can be performed. Since the dancers' ages are measured in seconds, the values can be very large.

Yankovich works as Software Engineer in a company called POI (Party Online Infinitely), as the name suggests it is a company that promotes online parties. To test the systems some employees threw parties and invited only the company employees with some restrictions.

The company employees form a hierarchical structure, where each one has a direct manager (except the company owner), and has no cyclic relations. Due to the company's promotion processes, the age of an employee is not greater than the age of his direct manager.

These initial parties work in the following way:

• Each party $$$j$$$ has an owner $$$O_j$$$ and an age range, from $$$L_j$$$ to $$$R_j$$$ .
• To be invited to a party an employee needs to have age inside the age range $$$[L_j, R_j]$$$ of the party. It is guaranteed that the age of the owner of each party is inside the age range of their parties.
• Besides the age restriction, to be invited to a party an employee must work directly with another employee that will be invited (as direct manager or direct subordinate), except for the party owner.

Yankovich is responsible for the application that computes data about the parties a user has participated. As an initial task he has to calculate how many parties an employee was invited to. Since he is late to deliver his first task, help him calculating this information for these initial parties.

The Commission for the Regional deveLopment of Fastminton (CRLF) organizes annual tournaments of the novel and unusual game of Fastminton, a Badminton derivative. CRLF is proud to be organizing the third big tournament, that will be held this year.

The commission's former programmer has developed a computerized system to capture and store the results from the matches, point by point, to individual files. He left before being able to complete a parser to the files, so the CRLF requires your help to guarantee that all the records can be read from the written files, to avoid loosing years of thrilling game results.

A summary of the Fastminton rules was given to you to help in your tasks. It is, in essence, a shorter (or faster) version of Badminton:

• Fastminton matches are always played with two opposing players in a court that is divided by a net;
• Players are identified by their relative positions on the score (left and right player);
• A match is composed of three games. The player that reaches $$$2$$$ games is the winner;
• A game is won when a player reaches at least $$$5$$$ points with a at least a $$$2$$$ point difference from his opponent, or by reaching $$$10$$$ points (whichever comes first);
• The left player begins serving on the first game. For all other games, the serving player is the one that won the last game;
• Every round results in a point for the server or the receiver player. The player who scores serves the next round.

The Society of Bright Competitors (SBC) organizes television shows to its members (and currently it also broadcasts online!). SBC uses a a system of credits called sbecs, which can be used by players to participate in competitions or can be exchanged for prizes at the end of each season. SBC started a new type of game, and needs to do some simulations to avoid very large losses in the prize pool!

Ricardo is going to try the new game. He must bet $$$100$$$ sbecs, which are transferred to his game balance. Then, a sequence of boxes is positioned. The game consists of rounds, and the maximum number of rounds is equal to the number of boxes. At each round, Ricardo decides whether to open the next box or to quit the game. If Ricardo quits, he gets the current balance of sbecs back. If Ricardo opens the next box, its content, which is a secret number, is added to his balance and the game continues. As the secret number in the box may be negative, Ricardo may end up at a loss! The game ends when Ricardo decides to quit or when the last box is opened.

SBC hired you to test the game. From the content of the boxes, you must decide what would be the largest possible balance that Ricardo could get.

A small cargo plane of the System of Binary Cargos (SBC) was designed to transport special and secret products. These products are grouped in boxes with different weights.

The plane has a safety weight range, within which the aircraft is stable. More specifically, there is an interval such that if the total weight of the boxes carried is not in the interval, then it will not be possible to guarantee the security of the flight.

It is known that all boxes have different weights. Moreover, given any two boxes, the heavier one weighs at least twice as much as the lighter box.

Your task is to determine in how many ways you can choose a specified number of these boxes to be transported on the plane without destabilizing it.

One day, Alice challenged Bob with the interactive programming problem described below.

You have a tree (an acyclic connected graph). Each node of the tree has exactly one parent, except the root node, which has no parent. Nodes that are not parents of any nodes are called leaves. You know the structure of the tree, because you know the parent of each node that is not the root.

Each node contains an integer value. A node that is not a leaf contains the sum of the values of all its direct children. Thus, all the values in the tree are determined by the values contained in the leaves.

The picture below depicts an example. The leaves are marked as gray, while the other nodes are white. Each node shows the value it contains.

Initially, you don't know any of the node values, but you can query them one by one. Your task is to figure out the value of each node in the tree, making as few queries as possible.

Bob solved this problem very easily. Then, to spice things up, Alice asked him: "given the tree structure, how many different solutions to this problem exist?" That is, how many different minimal sets of queries exist that allow one to figure out all the values stored in the tree? (Two sets of queries are considered different if and only if there is a node that is queried in one set but not in the other.)

Acre and Amanda are very curious and are always looking for patterns around them. They routinely collect and analyze data from various sources (city traffic, rainfall, number of leaves that fall from trees), hoping to find interesting patterns.

Their last expedition produced a very promising data set: it followed a perfectly straight line! Formally, it was a list of $$$N/2$$$ pairs of integers, possibly repeated. When these pairs were plotted as points in the Cartesian plane, all of them were perfectly collinear! Pleased, Acre and Amanda stored this data as a table containing the pairs of integers.

Unfortunately, while Acre and Amanda were out collecting more data, their infant son entered their office and scrambled the data table, by shuffling all the values in it. Now, all Acre and Amanda have left are the $$$N$$$ shuffled integers. They want to try to reconstruct the original data table from them.

Formally, Acre and Amanda want to arrange these integers into $$$N/2$$$ pairs, where each pair represents a point in the Cartesian plane, in such a way that all these points are collinear. The given list of integers can have repeated values, and each value must be used exactly as many times as it appears in the list. The resulting data set can also have repeated data points.

Since there may be several different suitable datasets that can be formed with the given integers, Acre and Amanda want to know the number of such datasets. Two datasets are considered different if and only if there is a point that appears more times in one data set than in the other.

Ties are usually an issue on elections and games. Recently, a new game, called Between Us, was created. The game is played by a number of players over a social network. On each turn, there are multiple votings, where a player may receive only votes from friends. The player getting the largest number of votes wins the game.

The game is still in its design phase, but the game developers faced a very common issue: since the number of friends of a given player is usually small, ties are very common, which makes the game less fun. To avoid this situation, they decided to add a new module to the match-making system, where it will try to form groups of players such that each player has an odd number of friends in the same group.

This problems turned out to be more challenging than they expected and they are now focusing on a simpler variation: given a set of players, the module must find a partition of the players in at most two groups, satisfying the restriction that each player must have an odd number of friends in his group. The problem is that this partition is not always possible. Your task is to determine whether the partition is possible.

Word Search is a well-known hobby, although it is losing some of its prestige in recent years. The goal in this game is to find words in an array, where each cell in this matrix contains a letter.

Bibika and her brother were playing Word Search, but soon they lost interest in the game, as finding all the words was getting relatively easy. Bibika would like to take her brother away from the computer, she searched the internet for games of the same style and ended up finding the Lavaspar Hunting.

Lavaspar Hunting is a game that follows the same idea of the famous Word Search. However, instead of simply having to find a word in the matrix, the goal is to find any anagram of the word, making the game more difficult and interesting. The anagram can be found in a row, column or diagonal.

An anagram is a word formed by rearranging the letters of another. Sometimes, an anagram does not exist as a word in the language, but this does not matter. balo, loba and aolb are examples of anagrams of the word bola.

Bibika realized that it was possible for the same cell in the matrix to make part of anagrams of different words and then she started to call these special cells.

Now she would like to know, given an array configuration and a collection of words, how many special cells are there?

The picture above illustrates the first example, where the collection of words consists of three words: bola, casa and boi. The rectangles of each color represent anagrams of different words from the entry. The $$$3$$$ special cells are painted yellow.

Fulanito plays an old-school arcade game. In the game, he can place a machine gun anywhere within his base, which contains all $$$(x, y)$$$ points with $$$x \lt 0$$$. There are $$$N$$$ enemies on the battlefield. The $$$i$$$-th enemy $$$(1 \le i \le N)$$$ is at position $$$(x_i, y_i)$$$ with $$$x_i \gt 0$$$. All these positions are given in advance.

A machine gun at $$$(x_m, y_m)$$$ covers an angle of vision to the right, centered on the line $$$y = y_m$$$, and whose borders are given by lines $$$y = y_m \pm \frac{x-x_m}{2}$$$. When placed, it kills all enemies within such angle, including its border lines.

Figure 1: Pictorial representation of the sample input

The scoring system used by this videogame is extremely awkward: many believe that it was in fact a horrible bug by the game developers, who then proceeded to just yell "it's not a bug, it's a feature!" to anyone asking about it. Specifically, the score achieved by a certain placement of the machine gun is calculated by executing the following steps:

• Take the ids ($$$i$$$ between 1 and $$$N$$$) of all the enemies that it kills.
• Sort all those ids in increasing order.
• Let the sorted values be $$$i_0 \lt i_1 \lt \dots \lt i_{k-1}$$$
• Compute the score as $$$\left(\sum^{k-1}_{j=0} i_j \cdot 5782344^j\right)\mod (10^9 + 7)$$$
• Note: A machine gun that kills no enemies gets a score of exactly $$$0$$$ points.

To get better at this game, Fulanito is going to ask you $$$q$$$ questions: each question asks the score that would be achieved by placing the machine gun at a certain $$$(x_m, y_m)$$$.

To make the problem more challenging, each $$$(x_m, y_m)$$$ is not given directly. Instead, values $$$a$$$ and $$$b$$$ are given, such that $$$x_m = -1 - \left( (p + a) \mod (10^9 + 7) \right)$$$ and $$$y_m = (p + b)\mod (10^9 + 7)$$$, where $$$p$$$ is the answer to the previous query ($$$p = 0$$$ when processing the first query).

NOTE: It is guaranteed that in total, taking all queries together, the number of killed enemies is at most $$$10^6$$$.

$$$1 \le x_i, y_i \le 10^9$$$.

$$$1 \le N, q \le 10^5$$$.

$$$0 \le a, b \lt 10^9 + 7$$$.

Eugenius is a very bright mathematician who enjoys multiplying numbers.

Once, he found $$$M$$$ nodes written on a piece of paper, numbered from 1 to $$$M$$$, we call these $$$M$$$-nodes. Each node $$$i$$$ was labeled with a unique prime number $$$p_i$$$, such that the primes were ordered (i.e. if $$$i \lt j$$$ then $$$p_i \lt p_j$$$).

Later on, he decided to draw $$$N$$$ new nodes, called $$$N$$$-nodes, and add edges between nodes in $$$M$$$ and nodes in $$$N$$$. He was very careful not to connect an $$$M$$$-node with an $$$M$$$-node, nor an $$$N$$$-node with an $$$N$$$-node; he wasn't as careful regarding how many edges between any two nodes he drew.

And just like that, he ended up with a bipartite multigraph.

As he mainly enjoyed multiplying numbers, he decided to label each $$$N$$$-node with the multiplication of all $$$M$$$-nodes that were directly connected to it; where each $$$M$$$-node was multiplied as many times as edges were between them.

Each $$$N$$$-node $$$i$$$ ended up being labeled with a number $$$c_i$$$. Then, the following formula characterizes each $$$c_i$$$:

$$$$$$ c_i = \prod_{(j,i) \in E} p_j, $$$$$$

where $$$E$$$ is the multiset of added edges, and every edge $$$e$$$ satisfies $$$e \in M \times N$$$. Later on, Eugenius decided to grab something to eat. While he was enjoying his torus, he accidentally spilled coffee on the labels $$$p_i$$$ and they disappeared.

Can you help him recover those sorted prime numbers?

The Human Colony at Venus is thriving! Here, the main form of public transportation is the Venusian Shuttle: it is a round flying disc, with windows and seats all around its border. In this shuttle, all the seats are window seats. And people are not allowed to move from one seat to another. So once someone chooses a seat, they must remain there until they leave the shuttle.

Even though it is a fully autonomous vehicle, every shuttle operates with an engineer on board, to handle any unexpected problems. You are Shuttle 1C9C's engineer, and you spend most of your work shift reading books. The problem is that you hate being exposed to the sun. Therefore, you want to choose a place to sit that minimizes the total amount of sunlight you take along your entire work shift.

The colony is represented by the Cartesian plane, where the $$$X$$$ axis points east and the $$$Y$$$ axis points north. The days at Venus are very long (in fact, longer than the year!), so you can assume that the sun always shines from the east direction. That is, the sunlight always travels west, in the negative $$$X$$$ direction.

See the figure below. The more your window is turned east, the more sunlight you're exposed to. But if your window is turned west, you're not exposed to the sun at all.

Formally, suppose the vector $$$(D_x, D_y)$$$ represents the direction faced by your window. Note that you only get any sunlight if $$$D_x \gt 0$$$. And let $$$\theta$$$ be the angle between the vectors $$$(D_x, D_y)$$$ and $$$(1, 0)$$$ (a vector pointing directly towards the sun). If $$$\cos(\theta) \le 0$$$ then you don't get any sunlight. Otherwise, you receive $$$\cos(\theta)$$$ units of sunlight per second.

The shuttle route consists of a sequence of stations around the colony. The shuttle starts the work shift at the first station, visits all stations in order, and then returns to the first one.

The shuttle always follows a straight line when going from one station to another, moving with constant speed of one meter per second. And although the shuttle is round, it has a "front side": this side is always facing the direction it is moving forward, and the shuttle rotates accordingly when it changes direction at the stations.

You may ignore time spent turning the shuttle around, picking up or dropping off passengers.