The mayor of Soteropolis, Betinho, which is known for his exotic tastes and for expending public money on unreasonable things, now decided to buy a Multiset Machine. A Multiset Machine can be represented by a DAG (directed acyclic graph) where each node represents an unary operation and each arc represents data flowing. The type of data that goes through an arc is a multiset of integers.

The incoming arcs of a node represent the input for such operation. If there are multiple incoming arcs, then the actual input for the operation is the sum of the multisets represented by those arcs.

The outgoing arcs of a node represent the output for such operation. The output is a single multiset of integers. If there are multiple outgoing arcs, then this multiset is replicated through all those arcs.

There are 4 types of nodes in a Multiset Machine. Some of them may have restrictions on the number of incoming/outgoing arcs. Also, they may have parameters which are properties of each node.

• source $$$v_1, \dots, v_k$$$ – this node may have incoming arcs or not. If it has, then let $$$I$$$ be the input multiset. Then this node outputs $$$I + \{v_1, \dots, v_k\}$$$. Otherwise, it outputs $$$\{v_1, \dots, v_k\}$$$.
• print – this node has no output. It prints the $$$k$$$-th smallest element of the input multiset. If there is no such element, then it prints -1. There is exactly one node of this type.
• select $$$k_1, k_2$$$ – this node has at least one incoming arc. It outputs a multiset comprised by a range of elements, from the $$$k_1$$$-th smallest element to the $$$k_2$$$-th smallest element of the input multiset. Every other element is ignored. This operation may produce less than $$$k_2 - k_1 + 1$$$ elements if for some $$$k_1 \leq i \leq k_2$$$ there is no $$$i$$$-th smallest element in the input multiset. In particular, if there is no $$$k_1$$$-th smallest element it will output an empty multiset.
• generator $$$a, b, M$$$ – let $$$I$$$ be the input for this node, or $$$\emptyset$$$ if there is no input. This node outputs $$${I + \{ y \;|\; 0 \leq y \lt M \; \texttt{and} \; \exists x, ax + b \equiv y \mod M \}}$$$.

Every node with no incoming arc is necessarily a source or a generator, and every node with no outgoing arc is necessarily a print. When the machine is turned on, the data starts flowing from the nodes which have no input. A node will only process and output something when all of its inputs have been received. It is also guaranteed that the machine will eventually print something.

Your task is to write a program that, given the structure of the mayor's Multiset Machine, is capable of printing the same number that his machine would print if it was turned on.

Piva has recently bought a wonderful beach house at Praia do Forte.

After deciding that his house would be as colorful as a rainbow, Piva painted his living room in tiles of different colors. More specifically, Piva's living room can be seen as a row of $$$n$$$ tiles such that the $$$i$$$-th of them has color $$$s_i$$$, where $$$s$$$ is a string composed of lowercase English characters.

Piva now wants to put his brand-new color changing sofa in his room. The sofa is $$$m$$$ ($$$m \leq n$$$) tiles long and should be put in the room in a way that it fits entirely on $$$m$$$ consecutive tiles. Moreover, Piva wants the colors of the sofa and of the floor to match. We say that their colors match if the color of a sofa tile matches with the color of the floor tile right below it. To accomplish that, Piva may change the colors of the sofa according to its specification.

The sofa can be described by a string $$$t$$$ of zeroes and ones of length $$$m$$$, where each character in the string represents a tile of the sofa. Piva can pick the zero-tiles and change them all to the same color. The same can be done for one-tiles. Therefore, notice that it is impossible for two zero-tiles (same for one-tiles) to have different colors. Also, that means that the tiles of the sofa will have at most two different colors. For instance, suppose the string is 101. That means we can color the sofa aba or aaa, but not abc.

Given the descriptions of Piva's living room and of his sofa, determine on how many positions his sofa can be placed. Notice that for each possible placement, the sofa colors can be chosen independently. Also, notice that the sofa can be put in any direction (left to right or right to left), but a position where it can be put in both directions should be counted only once.

Renan was driving the Cirque Du Soleil artists in his blue towner. Unfortunately the towner rolled over in Paralela (a well known avenue in Soteropolis). The $$$N$$$ circus performers have each a distinct value between $$$1$$$ and $$$N$$$. During the rollover the performers left the towner through the window, while doing some acrobatics and leaving poor Renan by himself inside the vehicle.

Everyone knows that Paralela is the habitat of an infamous Jaguar. This Jaguar wants to ambush the performers and get some food. Let $$$S$$$ be the value of satisfaction of its lunch. $$$S$$$ follows a totally arbitrary formula that can be calculated as shown below:

where $$$P$$$ is the set of performers $$$\{1, 2, \dots, N\}$$$, $$$\max(T)$$$ is the maximum value in $$$T$$$ and $$$\min(T)$$$ is the minimum value in $$$T$$$.

Renan feels like he could be in trouble, so he wants to know the satisfaction the Jaguar will get by ambushing the performers. Since Renan is not good at maths, you need to calculate $$$S$$$ for him. Note that this value can be big, so you only need to output it $$$S$$$ module $$$10^9 + 7$$$.

The Carnival is the biggest street festival in Soteropolis. It occurs in the very beginning of every Soteropolitan year and attracts a lot of people from around the globe. For the citizens of Soteropolis, though, it is actually a 50-50 situation: half of them love it, half of them hate it. That mainly occurs because it gets hard to transit in the city during the festival.

The mayor is planning to hold some tests before the actual Carnival. These tests are usually very small festivals which take place in a street of Soteropolis. During a festival, the street where it takes place gets blocked. Some of the streets of the city are called critical, but first we need to understand how the road system of Soteropolis was designed.

Soteropolis is composed by $$$n$$$ junctions directly connected by $$$m$$$ one-way streets. A street $$$(u, v)$$$ means that a car can go from $$$u$$$ to $$$v$$$ but not the other way around. Also, Soteropolis was carefully designed such that from every junction it's possible to get to every other junction using the existent streets. A critical street is a street that, when blocked, makes it impossible to get from some junction $$$u$$$ to some other junction $$$v$$$.

The mayor wants to hold a test festival. Your task is to decide which roads are critical and should be avoided.

After having a wonderful time at the Carnival test festival, Jão and his friends decided to go for an after party in his house. At some point Jão convinced them to play a classical mathematical puzzle. He put his friends in a line and gave each one of them a typical Carnival hat colored in black or white. They were arranged in such a way that they could only see the hats of people that were in front of them. In particular, the last person could see everyone's hat and the first could see nothing.

This game must be played from the last one on the line to the first. Each person should try, in this order, to guess the color of his own hat out loud. For that, the participants can agree on some strategy before getting the hats.

Jão had so much fun watching his drunk friends trying to tackle the puzzle. Now he decided to teach them a powerful strategy. Let $$$n$$$ be the number of participants in the game, and let they have numbers from 1 to $$$n$$$, from the first person in line to the last. Let the black hat have an associated value of $$$1$$$ and the white one have a value of $$$0$$$. Then we can always guess at least $$$n-1$$$ values correctly by following this strategy:

1. The last one in line have no information about his own hat, so he should guess the xor ($$$\oplus$$$) of all the hats he can see;
2. The others players in line should do something different. Let $$$X$$$ be the xor of the values guessed by previous players. Let $$$Y$$$ be the xor of the hats the current player can see. If $$$X = Y$$$, then his own hat must be white, otherwise it must be black;

Notice that every player will follow (2), except for the last one in line, which will follow (1). This strategy ensures that the first $$$n-1$$$ participants in line will guess correctly. Can you see why it works?

Unfortunately, Jão's friends are drunk, so they tend to mess the strategy up. When someone messes up, that means that he should have guessed $$$x$$$ according to the strategy, but guessed $$$x \oplus 1$$$. Your task, given the guesses of each participant in line, is to decide if there is a hat distribution such that we can say no one messed up given those guesses.

Renanzinho is a slow weirdo. In his 8th aniversary, there were candies, clowns, bouncers and even a delicious strogonoff. For him, the best part of the party, though, was unwrapping the gifts.

Renan, his father, gave to him $$$N$$$ toys. The height of the $$$i$$$-th toy is given by $$$A_i$$$. Renanzinho loved the toys and is planning to spend the night rearranging them. He wants to arrange his toys into groups such that every group has a size between $$$L$$$ and $$$R$$$ and contains only contiguous toys (every group of toys is a contiguous subsequence of $$$1, 2, \dots, N$$$). Also, every toy should be in exactly one group.

Suppose that Renanzinho splits his toys in $$$K$$$ groups. The happiness of Renanzinho is arbitrarily defined as the minimum value among the maximum toy height of each group.

Since Renanzinho is a slow kid you need to calculate the maximum happiness he can achieve if he splits the toys optimally.

The Barra Lighthouse is a famous touristic spot in Soteropolis. The lighthouse is 22 meters tall and its construction dates to 1698. At that time, the lighthouse was constructed right after the tragic wreck of the lead ship of the Commercial Soteropolis fleet.

It is known that the lamp of the lighthouse revolves in counter-clockwise direction with constant speed and a period of $$$T$$$ seconds. Also, it is known that the emitted light is a beam with a spread angle of $$$\alpha$$$ degrees (see the picture below), and that the person responsible for monitoring the coast can only see ships that are at most $$$d$$$ meters away from the lighthouse and that are lightened. We can imagine a system of two-dimensional coordinates with the lighthouse being on $$$(0, 0)$$$.

There are $$$n$$$ ships in the coast of Soteropolis. Those ships are all at bearth, so their coordinates won't change. The $$$i$$$-th of them is at coordinates $$$(x_i, y_i)$$$, $$$y_i \gt 0$$$. At the moment $$$t = 0$$$, the light beam has its center aligned with the x-axis positive direction, like in the picture shown above.

Your task is to compute, for each ship, for how much time it was visible to the guy in the lighthouse after $$$X$$$ seconds have passed.

Concurrently to the 2018 ICPC Regionals, a huge international Poker event is being held in Soteropolis. Professional poker players from all around the world joined amateur Soteropolis players for a weekend of poker.

Two poker players in the event can join to play a head-to-head all-in game of poker. The organization of the event imposed a predetermined restriction $$$n$$$ on the number of chips a player can have during a game. The number of chips the two players have can be denoted by a pair of integers $$$(x, y)$$$. In a valid game, $$$x, y$$$ should be between $$$1$$$ and $$$n$$$. Also, $$$x + y$$$ shouldn't exceed $$$n$$$.

An all-in game of poker is a game where players will always bet $$$min(x, y)$$$. In each turn, the winner will get $$$min(x, y)$$$ chips and the loser will lose as many chips. If after a turn one of the players have no chips, the game is considered finished. Otherwise, the game will continue.

Unfortunately, there are scenarios where the game can last forever. For example, in a game where the players have $$$(2, 1)$$$, if the player with less chips always win, the game will never end. The organization of the event want to prohibit every game that may possibly last forever.

The games which will for sure end in a finite number of turns are called finite. Even finite games may take a long time to finish. Let $$$t(x, y)$$$ be the maximum time a finite game with chips $$$(x, y)$$$ can last.

Your task is to compute the sum of $$$t(x, y)$$$ for every distinct $$$(x, y)$$$ that represents a valid finite game, given the predetermined restriction $$$n$$$.

Notice that $$$(x, y) \neq (y, x)$$$ if $$$x \neq y$$$. Also notice that an initially valid game will remain valid, even if it lasts forever.

After a year of hard work, Mano finally had a month off. He decided to take his grandmother to Soteropolis during this time. As soon as they arrived at the airport, Mano bought one of these "10 things to do in Soteropolis" travel guides. His grandmother instantly felt in love with pictures of the colonial mansions of Pelourinho, a historic neighborhood in western Soteropolis.

Pelourinho is a very big neighborhood. It is full of slopes and can be very trick for an elderly lady to explore. We can simplify its structure by imagining it as a line. The colonial mansions can be imagined as equally spaced spots on these lines: that is, from the $$$i$$$-th mansion (from left to right), you can go to mansions $$$i-1$$$ and $$$i+1$$$, if such mansions exist. These mansions are called neighbors of mansion $$$i$$$. Also, the $$$i$$$-th mansion is $$$h_i$$$ meters above sea level.

Mano knows that his grandmother will have serious difficulties in this kind of terrain. Your task is to write a computer program to answer some queries and help Mano plan his trip to Pelourinho. The two types of queries are described below:

• 1 $$$i$$$ $$$H$$$: the height of the $$$i$$$-th mansion should be set to $$$H$$$;
• 2 $$$i$$$ $$$H$$$: how many mansions Mano and his grandmother can visit if they start their trip at mansion $$$i$$$ and his grandmother can handle going from a mansion $$$u$$$ to a neighbor mansion $$$v$$$ iff $$$|h_u - h_v| \leq H$$$?

Write a program to process these queries.

Soteros is the biggest organized crime syndicate of Soteropolis. They are feared and respected. Members of Soteros follow a very rigid hierarchy. Sotero, the big boss, is the direct boss of some members, which in turn are direct boss of other members, and so on, like in a rooted tree structure. Therefore, Sotero is indirectly boss of the whole organization.

We can imagine a numbered rooted tree, where Sotero is represented by vertex $$$1$$$. The other $$$n - 1$$$ members are represented by numbers between $$$2$$$ and $$$n$$$. The direct boss of the $$$i$$$-th member is $$$p_i$$$. Notice that every one has exactly one direct boss, except for Sotero.

Soteropolis is a city with $$$K$$$ junctions and a bunch of two-way streets connecting pairs of these junctions. Soteros members have the culture of making themselves present on the streets. This is also true for the big boss Sotero. Every member of the organization is responsible for conducting business in at most one street of Soteropolis. More specifically, if the $$$i$$$-th member is responsible for some street, then junctions connected by this street are $$$u_i, v_i$$$.

Polo is an undercover agent working for SIA (Soteropolis Intelligence Agency) which finally got the chance to choose which member of Soteros he wants to work for. If he chooses to work for member $$$i$$$, then he will have free pass through all the streets that members (directly or indirectly) leadered by $$$i$$$ are responsible for, but he won't be able to traverse any other streets of the town.

Polo definitely want to keep a low profile, but he won't be able to do much if he can't move around the city. He asked you to make an analysis to help on his decision.

A connected region of Soteropolis is a maximal set of junctions such that for every pair of these junctions there is a path between them consisting only of streets Polo can freely traverse. In particular, an isolated junction (with no streets Polo can traverse around it) is a connected region.

For each member of Soteros, you should compute the number of connected regions Polo will be able to traverse if he chooses to work for such member.

João has just bought a new game from the store: Lampião, o Rei do Cangaço. The main character of the game is Lampião, a known figure of Soteropolitan culture and probably the most famous cangaceiro of all time. There is a lot of controversy around the reputation of the cangaceiros, but João definitely must stick to their cause to beat this game.

In this game, João must control Lampião through a series of mini-games. There is one mini-game that caught João's attention: the treasure hunt. In this mini-game, there are $$$n$$$ houses in a row, numbered 1 to $$$n$$$ from left to right. Lampião is supposed to break into some of these houses. After breaking into a house, Lampião may earn or lose coins (some houses are guarded by jagunços, which are dangerous mercenaries crazy for money). More specifically, let $$$C$$$ be how many coins Lampião possesses before breaking into the $$$i$$$-th house. Lampião will have $$$C + a_i$$$ coins after breaking into it, where $$$a_i$$$ may actually be negative.

Lampião is initially standing in front of one of the houses. Also, he initially possesses $$$10^9$$$ coins. The game is played in turns. The turns are numbered starting from one. In the $$$i$$$-th turn, one of the two actions below can be taken:

1. Move Lampião $$$3i$$$ houses to the right while breaking into every one of them, except for the final one. For instance, if this is the first turn, there are 4 houses, Lampião is standing by house 1 and this action is taken, Lampião will move to house 4 while breaking into houses 1, 2 and 3;
2. Just move Lampião $$$3i$$$ houses to the right.

The game instantly ends when Lampião goes beyond the $$$n$$$-th house.

Your task is to compute, for every possible starting position, the maximum profit Lampião can achieve if João acts optimally. The profit is defined as the difference between the final amount of coins and the initial amount of coins. Notice that the optimal profit is never negative, since João can choose not to take action (1).

The SIA (Soteropolis Intelligence Agency) has just engaged in a new operation code-named Hummingbird. It is responsible for the investigation of illegal biological activities in greater Soteropolis area. Tico is the one responsible for building a team for the operation. $$$n$$$ agents will be designated to it, but first they must be given code names and then be arranged hierarchically.

More specifically, Tico will arrange those $$$n$$$ agents in a line and number them from 1 to $$$n$$$, left to right. Right after that he will pick a code name for each one of the agents. The agent $$$i$$$ will receive a non-empty code name with at most $$$a_i$$$ characters. A code name is a string composed of:

• Zero or more digits from 0 to 9;
• At least one character from a set $$$S$$$ of special characters (this set doesn't contain digits from 0 to 9). The characters of this set form a total order. Therefore, given two distinct special characters $$$a, b$$$, we can say that $$$a \lt b$$$ or $$$b \lt a$$$.

Tico says that the strong character of a code name is the special character which is greater than all the others. For example, if we take $$$S$$$ as the set of English characters, the strong character of 4ak2k is k.

After that, Tico will choose a direct supervisor for each of the agents in such a way that the following properties are met:

• Each agent should have as a supervisor another agent, except for one of them, which will be the leader of the operation;
• Every agent should directly supervise at most two other agents;
• An agent can't (directly or indirectly) supervise himself. Therefore, the supervising relation forms a rooted binary tree;
• For each agent $$$i$$$, let $$$s_1, s_2, \dots, s_k$$$ be the ordered sequence of agents directly or indirectly supervised by him. If $$$s$$$ is non-empty, then $$$max(s_k, i) - min(s_1, i)$$$ should be equal to $$$k$$$. In other words, every sub-tree of this tree must be formed by agents from a contiguous subsequence of $$$1, 2, \dots, n$$$;
• The strong character of an agent's code name should be no smaller than the strong characters of the code names of the agents he supervise.

Tico defines a team as a pair of sequences $$$(g, p)$$$ such all the properties above are met, where $$$g_i$$$ is the code name of the $$$i$$$-th agent and $$$p_i$$$ is the supervisor of the $$$i$$$-th agent (or 0 if he is the team leader).

Tico is interested in counting how many distinct teams he can get by picking code names and supervisors for the agents. More specifically, he wants to count that for many different sets $$$S$$$.

Two teams $$$(g, p), (t, s)$$$ are considered different iff there is an agent $$$i$$$ such that $$$g_i \neq t_i$$$ or $$$p_i \neq s_i$$$.

Betinho, the mayor of Soteropolis, striked (the public coffers) again! Now he bought a Sorting Machine.

A Sorting Machine is a dedicated processor with 1000 cores and a shared memory capable of storing an array of integers. In one operation, one can select up to 1000 disjoint intervals of this array and sort them concurrently. The cost of such operation is the maximum between the costs of sorting each of these intervals independently.

The cost of sorting a single interval is $$$L \lceil \log_2(K + 1) \rceil$$$, where $$$L$$$ is the size of the interval and $$$K$$$ is the number of adjacent inversions it has. An adjacent inversion is a valid index $$$i$$$ such that $$$a_i \gt a_{i+1}$$$.

Netinho wants to use his machine to sort the sequence $$$n, n-1, n-2, \dots, 2, 1$$$. He wants to do at most 10 operations to sort this sequence, and he wants the total cost to be no more than $$$7n$$$. Find him a valid sequence of operations.