Symmetry in everyday language refers to a sense of harmonious and beautiful proportion and balance. In mathematics, "symmetry" has a more precise definition, that an object is invariant under any of various transformations; including reflection, rotation or scaling.

The axis of symmetry of a two-dimensional figure is a line such that, if a perpendicular is constructed, any two points lying on the perpendicular at equal distances from the axis of symmetry are identical. Another way to think about it is that if the shape were to be folded in half over the axis, the two halves would be identical: the two halves are each other's mirror image. Thus a square has four axes of symmetry, because there are four different ways to fold it and have the edges all match. A circle has infinitely many axes of symmetry passing through its centre, for the same reason.

In this problem, you are given $$$n$$$ rectangles with sides parallel to the coordinate axes on the 2D Cartesian plane. The area of the intersection of any two rectangles is zero. Your task is to find the axes of symmetry of the figure formed by these rectangles.

In computer science, a binary tree is a rooted tree in which each node has at most two children. In this problem, let's denote $$$n$$$ as the number of nodes, $$$l$$$ as the number of leaf nodes and $$$h$$$ as the height of the tree (a tree consisting of only a root node has a height of $$$0$$$).

Alice and Bob are playing a game with a binary tree. In this game, Alice and Bob have a binary tree, in which node $$$1$$$ is the root. They take turns to perform operations on the tree, and Alice always takes the first turn. In each operation, the player taking the turn must choose a node $$$p$$$ (any node including the root can be chosen), and remove the subtree rooted at $$$p$$$ from the tree. Obviously, the remaining graph, if not empty, is still a binary tree. Then they continue to play with the resulting tree. To make the game more interesting, there is a restriction on which nodes can be chosen as $$$p$$$: the subtree rooted at $$$p$$$ (the subtree to be removed) must be a perfect full binary tree. Note that a perfect full binary tree is a binary tree in which all interior (non-leaf) nodes have two children and all leaf nodes have the same depth. It can be easily shown that in a perfect full binary tree, the equation $$$l=2^h$$$ holds, so does the equation $$$n=2^{h+1}-1$$$. In particular, a tree consisting of only a root node is also a perfect full binary tree. When a player is unable to perform a legal operation, the game ends and that player loses, which means the other player wins.

Three examples of perfect full binary trees.

Alice and Bob are both very smart and always play optimally. Can you determine who would win the game?

Ranching and the cowboy tradition originated in Spain, out of the necessity to handle large herds of grazing animals on dry land from horseback. During the Reconquista, members of the Spanish nobility and various military orders received large land grants that the Kingdom of Castile had conquered from the Moors. These landowners were to defend the lands put into their control and could use them for earning revenue. In the process, it was found that open-range breeding of sheep and cattle (under the Mesta system) was the most suitable use for vast tracts, particularly in the parts of Spain now known as Castilla-La Mancha, Extremadura and Andalusia.

The historic 101 Ranch in Oklahoma, US. Public domain.

Jace is an employee at the International Cattle Production Company (ICPC), whose mission today is to help his client Karn to build a new cattle ranch. Both Jace and Karn agree that the ranch should be surrounded by fences to ensure security, and the shape of the ranch should be a simple polygon. Recall that a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments that are joined to form a single closed path. A simple polygon always has a measurable and strictly positive area.

There are $$$n$$$ shops selling fence segments in the town where Karn lives, they are numbered from $$$1$$$ to $$$n$$$ for convenience. Exactly $$$n-1$$$ bidirectional roads are connecting the shops, and there is exactly one simple path to travel between any two shops using those roads. In other words, the shops and roads form a tree in graph theory. The $$$i$$$-th shop only has a single fence segment for sale, whose length is $$$a_i$$$. Jace plans to travel from one shop $$$x$$$ to another shop $$$y$$$, and buy all fence segments from the shops on the only simple path from $$$x$$$ to $$$y$$$ (including $$$x$$$ and $$$y$$$). Then, he will try to build the fence (as mentioned above, it must be a simple polygon) with the segments he has bought. Since Karn doesn't want to waste any money, Jace must use all the segments in the fence. Please help Jace calculate how many pairs $$$(x,y)$$$ are there such that $$$x \lt y$$$, and Jace can build a valid fence if he travels from $$$x$$$ to $$$y$$$.

Microsoft Excel is a spreadsheet developed by Microsoft. It features calculation, graphing tools, pivot tables, and a macro programming language called Visual Basic for Applications. It has been a very widely applied spreadsheet for many different operating systems, especially since version 5 in 1993, and it has replaced Lotus 1-2-3 as the industry standard for spreadsheets.

In Excel, the labelling for columns uses upper case letters instead of numbers to distinguish it from the labelling for rows. The first column in Excel is labelled $$$A$$$, the second is labelled $$$B$$$ and so on. And after column $$$Z$$$, the next columns are labelled $$$AA, AB, \cdots, ZZ, AAA,\cdots$$$.

In this problem, we'll define a new labelling scheme. Let's use numerical digits instead of letters, and only a subset of the digits. Let's define base $$$k \ (2 \le k \le 10)$$$ labelling as using only digits from $$$10 - k$$$ to $$$9$$$ in the labels. For example, the labels in base $$$10$$$ in ascending order are $$$0, 1, \cdots , 9, 00, 01, \cdots$$$, and in base $$$7$$$ they are $$$3, 4, \cdots, 9, 33, 34,\cdots$$$.

Now, given $$$k$$$ and $$$X$$$, your task is to find the $$$X$$$-th label in base $$$k$$$.

After a long statistics lecture, the students are about to leave the classroom when it suddenly starts to rain heavily. Since you don't have your umbrella with you, you decide to stay in the classroom and hope the rain will end soon. Several minutes later, you are the only person still left in the classroom. You realize something interesting: there are $$$N$$$ ($$$N$$$ is odd) distinct integers written in a line on the blackboard. Because you are very bored, you decide to erase those numbers from the blackboard so that the janitor will have less work to do.

Piece of chalk and blackboard. Public domain.

Since you have just learned the concepts of median during the lecture, you invented the following erase-operation for three integers: wipe off the largest number and the smallest number from the blackboard, so that only the median of the three numbers remains. You decide to repeat the following process: choose three consecutive integers on the blackboard and apply erase-operation on them. After this operation, the number of integers on the blackboard will decrease by $$$2$$$. Eventually, there will be only one integer left after this process is repeated $$$\frac{N-1}{2}$$$ times. Suddenly, you come up with an interesting question: which integers may survive until the end?

On Sky Island, architects always use IslandClouds as materials to build all kinds of marvellous structures. Today, a sculpture competition is being held on Sky Island. Each architect needs to build some fancy sculptures with three kinds of meta IslandClouds. These three kinds of IslandClouds are in the shapes of spheres, cubes and regular tetrahedrons, and they come in different sizes. Of course, because they are clouds, once an IslandCloud touches another IslandCloud, they are glued together.

Asira, a famous architect on Sky Island, is now working hard on his great works. He is going to perform a series of operations to build his sculptures. In each operation, he picks an IslandCloud, rotates it and then moves it to someplace that is high enough, release it and let it fall down freely until it is glued to another IslandCloud or the ground (the ground of Sky Island is also made of IslandClouds). Asira will only release an IslandCloud after the previous one is glued.

Formally, you may assume the three types of IslandClouds are initially in the postures shown in the figures below, with their geometric centres at the world $$$(xyz)$$$ coordinates $$$(0, 0, 0)$$$ and the three object coordinate axes $$$(XYZ)$$$ each coincides with the corresponding world coordinate axes $$$(xyz)$$$. Here the world $$$(xyz)$$$ coordinates is assumed to remain motionless while the object $$$(XYZ)$$$ coordinates is solidary with the moving body which changes its orientation after each rotation.

An IslandCloud in the shape of a cube.

An IslandCloud in the shape of a sphere.

An IslandCloud in the shape of a regular tetrahedron.

To make a beautiful sculpture, Asira rotates the IslandCloud with the following process before letting it fall (it is called $$$zXZ-(\alpha, \beta, \gamma)$$$ proper Euler Angles):

1. The object $$$(XYZ)$$$ coordinates rotates about the $$$z$$$ axis by $$$\alpha$$$ together with the object. The $$$X$$$ axis is now at angle $$$\alpha$$$ with respect to the $$$x$$$ axis (according to the right-hand rule).
2. The object $$$(XYZ)$$$ coordinates rotates about the $$$X$$$ axis by $$$\beta$$$ together with the object.
3. The object $$$(XYZ)$$$ coordinates rotates about the $$$Z$$$ axis by $$$\gamma$$$ together with the object.

After that, the IslandCloud is moved so that its centre is at $$$(x, y, +\infty)$$$ in world coordinates and is then released. The $$$z$$$ coordinate starts to decrease as the IslandCloud falls until it touches another IslandCloud (any point on the falling IslandClould coincides with any point on another IslandClould). Once that happens, the IslandCloud immediately stops moving and becomes glued, which means it can never move again. Don't forget that the ground, which is the $$$xOy$$$ plane, is also made of IslandClouds.

Now, Asira wants to know the $$$z$$$ coordinate of the highest point of each IslandCloud once it is glued.

Tower defence games are the best games to kill time. In this kind of games, the player needs to build towers at certain candidate locations to defend a base building from monsters. The difficulty lies in that the budget for building towers is usually quite tight, and the player often needs to build towers at tricky locations in order to save resources while still being able to kill all the monsters.

Screenshot of a simple 1-bit tower defense game for Arduboy. Public Domain.

Let's consider a simplified version of the game: the map can be viewed as a rooted tree with at least two nodes, where the root is the base that the player needs to defend from monsters. Monsters will appear at each leaf node. When a monster appears, it goes up to the root node following the edges of the tree to attack the base. The player can build towers at any node of the tree including the root node. In this simplified game, we assume the towers are powerful enough that any monsters entering a node where a tower is built will be killed. Naturally, building towers at different nodes cost different amounts of resources and you need to defend the base (kill all the monsters) at the lowest possible cost.

Given the map, it's easy to calculate the optimal solution. However, this time you are not playing, but developing a tower defence game as your project for a course at your university. You are required to design a map (you need to give the structure of the tree and the cost of building towers at each node) that has exactly $$$K$$$ optimal solutions to defend the base. A solution is optimal if and only if it has the lowest cost among all possible ways to build towers that ensure all monsters are killed. Two solutions are considered different if and only if there is at least one node such that in one solution a tower is built on this node, and in the other solution no tower is built on it.

Trench warfare is a type of land warfare using occupied fighting lines largely comprising military trenches, in which troops are well-protected from the enemy's small arms fire and are substantially sheltered from artillery. The most famous use of trench warfare is the Western Front in World War I. "Trench warfare" has become a byword for stalemate, attrition, sieges, and futility in conflict. Trench warfare proliferated when a revolution in firepower was not matched by similar advances in mobility, resulting in a gruelling form of warfare in which the defender held the advantage.

Trench diagram from a 1914 British infantry manual. Public domain.

As a senior commander in the army, you must hold the ground with your soldiers. You have constructed a defence line consisting of $$$N$$$ trenches numbered from $$$1$$$ to $$$N$$$, each of which is empty initially. The soldiers are waiting for your order, and each soldier has a preferred shooting height.

As the battle goes on, the following two events may happen:

• A soldier with the preferred shooting height $$$h$$$ is sent to garrison an empty trench.
• An enemy with height $$$H$$$ is sighted, and only the soldiers garrisoned in trenches numbered between $$$L$$$ and $$$R$$$ can shoot that enemy. In order to improve the chance to hit and thus save the bullets, it is necessary to select a soldier whose preferred shooting height is as close as possible to the enemy's height to shoot the enemy. You need to know the difference between the selected soldier's preferred shooting height and the enemy's height.

Your deputy in charge of intelligence has predicted that $$$M$$$ events would happen during the battle. To make better preparations for the battle, you need to write a program to simulate the events and study the outcome.

The International Coalition to Prevent Catastrophes (ICPC) recently discovered several small asteroids in a nearby galaxy. If these asteroids hit the Earth, it will lead to a terrible disaster. So it is important for the ICPC to fully study the orbit trajectories of these asteroids. The ICPC consists of many member states, and due to the difference in development, they may have different goals in the study.

Orbits of Comet Kohoutek and the Earth. Public domain.

The ICPC has marked $$$n$$$ astronomy observatories around the world, labelled by $$$1,2,\cdots,n$$$. According to the ICPC's prediction, there will be $$$m$$$ events of two types, detailed below:

• "1 y k q[1..k]" ($$$1\leq y\leq 10^6$$$, $$$1\leq k\leq 3$$$, $$$1\leq q_i\leq n\text{ for } 1 \le i \le k$$$): A new member of the ICPC joins the study, whose goal is to gather at least $$$y$$$ minutes of video of the asteroids in total. The new member has $$$k$$$ cameras and is going to install exactly one camera in each astronomy observatory labelled by $$$q_1,q_2,\dots,q_k$$$. It is guaranteed that these $$$k$$$ integers $$$q_1,q_2,\dots,q_k$$$ are pairwise distinct. Let $$$p$$$ be the number of events of type 1 before this event, then this member is assigned the ID of $$$p+1$$$.
• "2 x y" ($$$1\leq x\leq n$$$, $$$1\leq y\leq 10^6$$$): Each the camera installed at the $$$x$$$-th astronomy observatory successfully gathers $$$y$$$ minutes of asteroid video. You need to report the number of ICPC members whose goals are just reached after this event, and the IDs of these members. Note that you shouldn't count the members whose goals have already been reached before this event.

You are an employee at the ICPC and your leader asks you to write a program to simulate these events, so that the ICPC may make appropriate preparations for the study.

Number theory is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss said, "Mathematics is the queen of the sciences—and number theory is the queen of mathematics." Number theorists study prime numbers as well as the properties of objects made out of integers or defined as generalizations of the integers.

Portrait of Carl Friedrich Gauss by C.A. Jensen. Public Domain.

Chandra is a junior mathematician who has just guaduated from university and she specializes in number theory. It has always been her ambition to become as famous a mathematician as Gauss. In her recent work, she invented a new function $$$f(x)$$$ for a postive integer $$$x$$$ during her recent research in number theory. Let $$$k$$$ be the number of digits in the decimal representation of $$$x$$$, and $$$d(x,i) \ (1 \le i \le k)$$$ be the $$$i$$$-th digit of $$$x$$$ in its decimal representation. Then $$$$$$f(x)=\sum_{i=1}^{k-1}\sum_{j=i+1}^{k} d(x,i) \cdot d(x,j)$$$$$$

Chandra has also found a mysterious integer $$$m$$$. She thinks that positive integers which satisfy the property $$$x \equiv f(x) \pmod{m}$$$ may be very important for her research. She wants to find out the number of such integers $$$x$$$ which also satisfy $$$L \le x \le R$$$. She only needs to know that number modulo $$$10^9+7$$$, which is another mysterious integer she has found during her research. Unfortunately, the numbers $$$L$$$ and $$$R$$$ can be very large and it is not feasible to solve that problem by hand, even for a mathematician. In order to publish her paper and become a well-known mathematician, Chandra asks you, a famous programmer, to help her overcome this obstacle in her research.

A blockchain is a growing list of records, called blocks, that are linked using cryptography. Each block contains a cryptographic hash of the previous block, a timestamp, and transaction data (generally represented as a Merkle tree). By design, a blockchain is resistant to modification of the data. It is called "an open, distributed ledger that can record transactions between two parties efficiently and in a verifiable and permanent way".

The Innovative Cluster Production Company (ICPC) recently decides to start a key research project related to blockchain, data mining, self-driving cars, and deep learning. There are $$$m$$$ algorithm engineers and $$$m$$$ software engineers in the ICPC. The ICPC wants to assign this new project to $$$k$$$ pairs of engineers, each of which consists of exactly one algorithm engineer and one software engineer. No engineer may be assigned to multiple pairs, otherwise the workload would be too high for the engineer.

There are $$$n$$$ buildings in the ICPC, standing sequentially one next to the other, labelled by $$$1,2,\cdots,n$$$ from left to right. The distance between the $$$i$$$-th building and the $$$(i+1)$$$-th building is $$$d_i$$$. For each engineer, we know the building where they are located, and the cost of assigning them to this project.

The two engineers in each pair need to be able to meet each other regularly to discuss the project. For each pair, the ICPC needs to pay $$$dis$$$ dollars for the cost of transportation, where $$$dis$$$ is equal to the distance between the buildings where the two engineers in the pair are located.

The ICPC is now looking for the pair assignment that minimizes the total cost of assigning engineers and transportation. Please write a program to help the ICPC find the cheapest assignment. Since key projects are the most important kind of projects for the ICPC, the details of the project must be further discussed, and the number $$$k$$$ is not yet decided. Therefore, you need to find the optimal assignment for each $$$k=1,2,\cdots,m$$$.