As an ACM-ICPC newbie, Aishah is learning data structures in computer science. She has already known that a stack, as a data structure, can serve as a collection of elements with two operations:

• push, which inserts an element to the collection, and
• pop, which deletes the most recently inserted element that has not yet deleted.

Now, Aishah hopes a more intelligent stack which can display the maximum element in the stack dynamically. Please write a program to help her accomplish this goal and go through a test with several operations.

Aishah assumes that the stack is empty at first. Your program will output the maximum element in the stack after each operation. If at some point the stack is empty, the output should be zero.

Bahiyyah has a convex polygon with $$$n$$$ vertices $$$P_0, P_1, \cdots, P_{n-1}$$$ in the counterclockwise order. Two vertices with consecutive indexes are adjacent, and besides, $$$P_0$$$ and $$$P_{n-1}$$$ are adjacent. She also assigns a point $$$Q$$$ inside the polygon which may appear on the border.

Now, Bahiyyah decides to roll the polygon along a straight line and calculate the length of the trajectory (or track) of point $$$Q$$$.

To help clarify, we suppose $$$P_n = P_0, P_{n+1} = P_1$$$ and assume the edge between $$$P_0$$$ and $$$P_1$$$ is lying on the line at first. At that point when the edge between $$$P_{i-1}$$$ and $$$P_i$$$ lies on the line, Bahiyyah rolls the polygon forward rotating the polygon along the vertex $$$P_i$$$ until the next edge (which is between $$$P_i$$$ and $$$P_{i+1}$$$) meets the line. She will stop the rolling when the edge between $$$P_n$$$ and $$$P_{n+1}$$$ (which is same as the edge between $$$P_0$$$ and $$$P_1$$$) meets the line again.

In cryptography, a Caesar cipher, also known as the shift cipher, is one of the most straightforward and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions up (or down) the alphabet.

For example, with the right shift of $$$19$$$, A would be replaced by T, B would be replaced by U, and so on. A full exhaustive list is as follows:

• The plaintext: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z;
• The ciphertext: T U V W X Y Z A B C D E F G H I J K L M N O P Q R S.

Now you have a plaintext and its ciphertext encrypted by a Caesar Cipher. You also have another ciphertext encrypted by the same method and are asked to decrypt it.

Duha decided to have a trip to Singapore by plane.

The airplane had $$$n$$$ seats numbered from $$$1$$$ to $$$n$$$, and $$$n$$$ passengers including Duha which were also counted from $$$1$$$ to $$$n$$$. The passenger with number $$$i$$$ held the ticket corresponding to the seat with number $$$i$$$, and Duha was the number $$$1$$$ passenger.

All passengers got on the plane in the order of their numbers from $$$1$$$ to $$$n$$$. However, before they got on the plane Duha lost his ticket (and Duha was the only passenger who lost the ticket), so he could not take his seat correctly. He decided to take a seat randomly. And after that, while a passenger got on the plane and found that his/her seat has been occupied, he/she selected an empty seat randomly as well. A passenger except Duha selected the seat displayed in his/her ticket if it had not been occupied by someone else.

The first problem you are asked to calculate in this problem is the probability of the last passenger to get on the plane that took his/her correct seat.

Several days later, Duha finished his travel in Singapore, and he had a great time.

On the way back, he lost his ticket again. And at this time, the airplane had $$$m$$$ seats numbered from $$$1$$$ to $$$m$$$, and $$$m$$$ passengers including Duha which were also counted from $$$1$$$ to $$$m$$$. The passenger with number $$$i$$$ held the ticket corresponding to the seat with number $$$i$$$, and Duha was the number $$$1$$$ passenger as well.

The difference was that: all passengers got on the plane in a random order (which was any one of the $$$m!$$$ different orders with the same chance). Similarly, Duha or a passenger who found his/her seat had been occupied selected an empty seat randomly.

The second problem you are asked to calculate in this problem is the probability of the last passenger to get on the plane that took his/her right seat on the return trip.

In computer science, a 2-3-4 tree, as a search tree, is a self-balancing data structure that is commonly used to implement dictionaries. The numbers mean a tree where every node with children (internal node) has either two, three or four child nodes.

A 2-node is the same as a binary node, which has one data element, and if internal has two child nodes. A 3-node has two data elements, and if internal has three child nodes. A 4-node has three data elements, and if internal has four child nodes. All leaves are at the same depth, and all data is kept in sorted order.

Here we introduce the procedure of inserting a value into a 2-3-4 tree. If the number of values that have been inserted in is no more than $$$2$$$, the 2-3-4 tree after the insertion has only one node (the root) with several data elements.

Otherwise, we start the following procedure at the root of the 2-3-4 tree.

1. If the current node is a 4-node:
   • Remove and save the middle value to get a 3-node
   • Split the remaining 3-node up into a pair of 2-nodes (the now missing middle value is handled in the next step).
   • If this is the root node (which thus has no parent):
     • the middle value becomes the new root 2-node and the tree height increases by 1. Ascend into the root (which means that the current node becomes the new root node).
   • Otherwise, push the middle value up into the parent node. Ascend into the parent node (which means that the current node becomes its parent node).
2. If the current node is a leaf, insert the value into the node and finish.
3. Otherwise,
   • Find the child whose interval contains the value to be inserted.
   • Descend into the child and repeat from step 1.

Now you are given a 2-3-4 tree which is empty at first. Then we insert $$$n$$$ values $$$a_1, a_2, \cdots, a_n$$$ into the 2-3-4 tree one by one. You are asked to write a program to print the 2-3-4 tree after inserting all the given values along the pre-order traversal. For a node with one or more data elements, your program will print these data elements in one line in ascending order.

Firdaws and Fatinah are living in a country with $$$n$$$ cities, numbered from $$$1$$$ to $$$n$$$. Each city has a risk of kidnapping or robbery.

Firdaws's home locates in the city $$$u$$$, and Fatinah's home locates in the city $$$v$$$. Now you are asked to find the shortest path from the city $$$u$$$ to the city $$$v$$$ that does not pass through any other city with the risk of kidnapping or robbery higher than $$$w$$$, a threshold given by Firdaws.

Byteland has $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$, and $$$n-1$$$ bi-directional roads connecting them. For each pair of cities, the residents can arrive one from another one through these roads (which also means the road network in Byteland is a tree).

Ghaliyah, the queen of the land, has decided to construct $$$k$$$ new factories. To avoid contamination, she requires that a factory can locate at a city with only one road (which also means this city is a leaf in the road network). Besides, a city can only have one factory.

You, as the royal designer, are appointed to arrange the construction and meanwhile, minimize the sum of distances between every two factories.

It is my great honour to introduce myself to you here. My name is Aloysius Benjy Cobweb Dartagnan Egbert Felix Gaspar Humbert Ignatius Jayden Kasper Leroy Maximilian. As a storyteller, today I decide to tell you and others a story about the hero Huriyyah, and the monsters.

Once upon a time, citizens in the city were suffering from $$$n$$$ powerful monsters. They ate small children who went out alone and even killed innocent persons. Before the hero appeared, the apprehension had overwhelmed the people for several decades.

For the good of these unfortunate citizens, Huriyyah set off to the forest which was the main lair of monsters and fought with $$$n$$$ fierce and cruel monsters. The health point of the $$$i$$$-th monster was $$$HP_i$$$, and its attack value was $$$ATK_i$$$.

They fought in a cave through a turn-based battle. During each second, the hero Huriyyah was attacked by monsters at first, and the damage was the sum of attack values of all alive monsters. Then he selected a monster and attacked it. The monster would suffer the damage of $$$k$$$ (its health point would decrease by $$$k$$$) which was the times of attacks it had been came under. That is to say, for each monster, the damage of the first time that Huriyyah attacked it was $$$1$$$, and the damage of Huriyyah's second attack to this monster was $$$2$$$, the third time to this monster was $$$3$$$, and so on. If at some time, the health point of a monster was less than or equal to zero, it died. The hero won if all monsters were killed.

Now, my smart audience, can you calculate the minimum amount of total damages our hero should suffer before he won the battle?

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Izdihar is an ACM-ICPC master and provides a pseudocode implementation about the bubble sort for you. The algorithm for a list of sortable items A can be expressed as (1-based array):

1. n = length(A)
2. repeat
   1. swapped = false
   2. for i = 2 to n inclusive do
      1. if A[i-1] > A[i] then
         1. swap( A[i-1], A[i] )
         2. swapped = true
         end if
      end for
   until not swapped

She says a permutation of $$$1$$$ to $$$n$$$ is almost sorted if the length of its longest increasing subsequence is at least $$$n-1$$$.

You are asked to count the number of permutations of $$$1$$$ to $$$n$$$ which, after $$$k$$$ times passing through the list in the bubble sort, would become an almost sorted permutation.

Jamilah is obsessed with nested triangles which share a common edge. Now she selects two points $$$P$$$ and $$$Q$$$ in the plane and calls them pivots. She also provides several other points $$$A_1,A_2,\cdots,A_{n-1}$$$ and $$$A_n$$$, none of which is lying on the line passing through the points $$$P$$$ and $$$Q$$$.

As the one with the same interest, you are asked to find the largest size of a group of nested triangles, and a feasible solution of the largest group with the smallest lexicographical order.

A group of nested triangles, with pivots $$$P$$$ and $$$Q$$$, is a list of selected points provided by Jamilah, denoted by $$$A_{v_1},A_{v_2},\cdots,A_{v_k}$$$, such that for any $$$i \ge 2$$$ the point $$$A_{v_i}$$$ is located inside the triangle $$$PQA_{v_{i-1}}$$$, excluding the border.

The solution $$$v_1,v_2,\cdots,v_k$$$ is the one with the smallest lexicographical order if, for any other feasible solution $$$u_1,u_2,\cdots,u_k$$$, $$$v_1 \lt u_1$$$ or there exists an integer $$$i~(1\le i \lt k)$$$ such that $$$v_1=u_1,v_2=u_2,\cdots,v_i=u_i$$$ but $$$v_{i+1} \lt u_{i+1}$$$.

In graph theory, a vertex cover of a graph $$$G$$$ is a set of vertices $$$S$$$ such that each edge of the graph is incident to at least one vertex of the set. That is to say, for every edge $$$(u,v)$$$ of the graph, either $$$u$$$ or $$$v$$$ is in the vertex cover $$$S$$$.

Now, Kamilah shows you an undirected graph $$$G$$$ without loops or multiple edges, each vertex of which has a weight. She can evaluate a vertex cover $$$S$$$ of $$$G$$$ by the product of weights of all vertices belonging to $$$S$$$. Here, the product of an empty set (of numbers) is defined as $$$1$$$.

You are asked to calculate the sum of the evaluations described above for all vertex covers of $$$G$$$.

Lamis is a smart girl. She is interested in problems about sequences and their intervals.

Here she shows you a sequence of length $$$n$$$ with positive integers, denoted by $$$a_1, a_2, a_3, \cdots, a_n$$$. She is amazed at those intervals, which is a consecutive subsequence of $$$a_1,a_2,\cdots,a_n$$$, with several continuous numbers, and names them continuous intervals.

More precisely, consider a interval $$$a_l,a_{l+1},\cdots,a_{r-1},a_r$$$ for instance where $$$1\le l\le r\le n$$$. If, after sorting the interval, the difference of any two neighbouring items is less than or equal to $$$1$$$, the interval will be considered as continuous.

As her best friends, you came from far and wide and travelled thousands of miles to Ningxia, to help her count the number of continuous intervals of the sequence.

The chromatic polynomial is a graph polynomial. It counts the number of graph colourings as a function of the number of colours.

Precisely speaking, for an undirected graph $$$G$$$, $$$\chi_G(k)$$$ counts the number of its vertex k-colourings. Here a vertex k-colouring of $$$G$$$ is an assignment of one of $$$k$$$ possible colours to each vertex of $$$G$$$ such that no two adjacent vertices receive the same colour. There is a unique polynomial $$$\chi_G(x)$$$ which evaluated at any integer $$$k\ge 0$$$ coincides with $$$\chi_G(k)$$$. If $$$G$$$ has $$$n$$$ vertices, the chromatic polynomial $$$\chi_G(x)$$$ is of degree exactly $$$n$$$ with integer coefficients.

Malak can use the chromatic polynomial to solve several interesting problems, including the question about acyclic orientation. In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph (DAG). Every graph $$$G$$$ has exactly $$$|\chi_G(-1)|$$$ different acyclic orientations, so in this sense, an acyclic orientation can be interpreted as a colouring with $$$-1$$$ colours.

Now Malak shows you a complete bipartite graph with $$$n$$$ and $$$m$$$ vertices in its two sets respectively, denoted by $$$K_{n,m}$$$. You are asked to count the number of different acyclic orientations of $$$K_{n,m}$$$.