In Japan, the multiplication table below is learned in elementary schools.

Such a table with $$$9\times9$$$ items, called kuku in Japanese, is not necessarily a world standard. In some cultures, $$$12\times12$$$ or $$$20\times20$$$ tables are learned.

Interestingly, the total of all the $$$9\times9$$$ items in the kuku table is 2025, which happens to be this year. Are there any other interesting cases like this?

Your task is to compute, for a given integer $$$n$$$, the sum of all the items in an $$$n\times n$$$ multiplication table. More specifically, find $$$$$$ \sum_{a = 1}^n \sum_{b = 1}^n ab. $$$$$$

In this problem, a prefix of a string means a consecutive substring starting from its first character. For example, the prefixes of the string icpc are i, ic, icp, and icpc. Similarly, a suffix of a string means a consecutive substring ending at its last character. For example, the suffixes of the string icpc are icpc, cpc, pc, and c.

Given a string $$$s$$$, find the shortest string other than $$$s$$$ itself having $$$s$$$ as both its prefix and its suffix. It can be proven that such a string is unique.

You are an enthusiastic worker. You want to know how many days you can work during the next specified number of days.

Saturdays and Sundays are non-working days. In addition, a number of national holidays and some company-specific days are non-working days. You cannot work on non-working days. Such non-working days may overlap: The founding anniversary of the company may coincide with a national holiday. Even when such non-working days coincide, there is no system to grant additional non-working days.

Today is Monday. Your task is to count the number of days you can work within a specified period starting from today.

In ancient Icpca civilization, games were played on a board covered with square tiles of the same size. It is certain that the tiles had either black or white surfaces, but their arrangement is not yet known.

One of the most influential theories says that the board was divided into square regions of the same size, each filled with the tiles of a single color, either black or white. It says that the regions had alternating colors, in both front-back and left-right directions, like a chessboard.

Today, a rectangular part of the board used in the game was discovered. Your task is to determine whether this artifact is consistent with the theory described above. If it is consistent, also determine whether the number of tiles as the side length of the square regions can be uniquely identified.

The artifact of the first test case of Sample Input 1 is shown on the left of Figure D.1. This artifact can be considered as part of a board where the square regions have sides of 2 tiles, as shown in the red frame on the right, and thus the artifact is consistent with the theory. Furthermore, since it cannot be a part of a board with square regions of any other size, the side length is uniquely identified to be 2 tiles.

Figure D.1: The first test case of Sample Input 1

The year is AD 3000. Humanity enjoys traveling among the stars via the network of interstellar spaceship routes. Due to recent advances in warp drive technology, however, the traditional spaceship routes are being gradually discontinued. You, a nostalgic voyager, have decided to take all the remaining routes before the planned discontinuation.

Currently, the interstellar routes form a tree-structured network among $$$n$$$ planets. That is, there are $$$n-1$$$ bidirectional routes each connecting two planets, and by taking such routes several times, you can travel between any pair of planets. However, each route has now been assigned its final boarding time. If you are on a planet at time $$$t$$$, and $$$t$$$ does not exceed the final boarding time $$$e$$$ of a certain route starting there (i.e., $$$t \le e$$$), you can reach the other end of the route at time $$$t+1$$$. You cannot use the route after the final boarding time.

In addition to the traditional spaceship routes, you can also use the new warp drive technology. Using the warp drive, you can instantly travel from any planet to a destination planet without spending any time, provided that you have already visited that destination at least once! You are currently on one of the $$$n$$$ planets. Because you have not visited any other planets prior to this journey, you must first travel to a planet via the spaceship routes before you can warp to it.

Starting your journey at time $$$0$$$, can you traverse all the spaceship routes before their respective final boarding times? Since the network forms a tree, the question is equivalent to asking whether you can visit all the planets. If such a journey is possible, find the order in which you should visit the planets.

Figure E.1: The first test case of Sample Input 1

Figure E.1 illustrates the first test case of Sample Input 1. The left part shows the network of interstellar spaceship routes. Each line segment is labeled with an integer representing the final boarding time of the route. The right part shows one way to traverse all the routes. Dotted lines in the right part represent warps, and the notation "$$$t\ldots t+1$$$" represents taking the route that departs at time $$$t$$$ and arrives at time $$$t+1.$$$

The videos showcasing a wide variety of tricks performed by your two pet dogs, Amy and Bessie, have become popular content in the Icpca Kingdom. To explore the potential for further videos, you taught the dogs a new trick.

The new trick is performed using plates aligned from left to right. Each plate holds either an apple or a banana.

When you command Amy, she holds a banana in her mouth and looks at each plate in turn from left to right. She skips any plate with a banana and, upon reaching the first plate with an apple, places the banana she was carrying on that plate, picks up the apple, and continues to the right. Then she skips any plate with an apple and, upon reaching the first plate with a banana, places the apple she was carrying on that plate, picks up the banana, and comes back to you, successfully completing the trick. If the fruits on the plates are not arranged in a way that allows this, the trick fails.

When you command Bessie, she holds an apple in her mouth and looks at each plate in turn from left to right. She skips any plate with an apple and, upon reaching the first plate with a banana, places the apple she was carrying on that plate, picks up the banana, and continues to the right. Then she skips any plate with a banana and, upon reaching the first plate with an apple, places the banana she was carrying on that plate, picks up the apple, and comes back to you, successfully completing the trick. If the fruits on the plates are not arranged in a way that allows this, the trick fails.

You cannot command both dogs simultaneously, nor can you command one dog while the other is performing a trick.

In the next video project, you want to rearrange the fruits on the plates into the target state by repeatedly having the dogs perform successful tricks. You are given the initial and target states of the fruits on the plates. Starting from the initial state, can you rearrange the fruits on the plates into the target state by issuing no more than a specified number of commands to Amy and Bessie in an appropriate order? If possible, find a sequence of such commands.

Two planes, $$$H_1$$$ and $$$H_2,$$$ are in a three-dimensional Euclidean space with axes, $$$x, y,$$$ and $$$z,$$$ where $$$H_1$$$ is defined by $$$z=1$$$ and $$$H_2$$$ by $$$z=2.$$$

You are given $$$n$$$ real numbers, $$$d_1, \ldots, d_n,$$$ and $$$m$$$ real numbers, $$$d'_1, \ldots, d'_m$$$. These real numbers are positive and strictly less than $$$180.$$$ Consider drawing the following convex polygons on the planes $$$H_1$$$ and $$$H_2$$$.

• On $$$H_1$$$, you draw an $$$n$$$-sided polygon. The interior angles at its vertices are $$$d_1, \ldots, d_n$$$ degrees in counterclockwise order as viewed from the origin.
• Similarly, on $$$H_2$$$, you draw an $$$m$$$-sided polygon. The interior angles at its vertices are $$$d'_1, \ldots, d'_m$$$ degrees in counterclockwise order as viewed from the origin.

Once the positions of the two polygons are fixed, the convex polyhedron whose vertex set is these $$$n+m$$$ vertices is uniquely determined. Write a program that enumerates all the possible numbers of faces that such a convex polyhedron can have.

Here, all the dihedral angles (angles between two adjacent faces) of a convex polyhedron must be strictly less than $$$180$$$ degrees.

In the first test case of Sample Input 1, quadrilaterals whose interior angles are all $$$90$$$ degrees are drawn on $$$H_1$$$ and $$$H_2$$$. For example, a rectangular cuboid can be constructed as in Figure G.1 (a), which has six faces. By rotating one of the quadrilaterals as shown in Figure G.1 (b), a convex polyhedron with ten faces can be constructed. The possible numbers of faces are six and ten.

Figure G.1: The first test case of Sample Input 1

A number of stamps are lined up from left to right in front of you, each engraved with an open parenthesis, '(', or a close parenthesis, ')'. First, you choose one of them and press it onto a piece of paper. The stamp is then returned to its original position. Next, you choose the stamp immediately to the left or right of the one you just returned, and press it directly next to the previous print. You repeat this operation of selecting either the left or right stamp and pressing it. During this process, you may select the stamp at the same position any number of times, but you may not select it consecutively.

A line consisting only of open and close parentheses will be printed on the paper. The printed line is valid if, counting characters in the line one by one from its start, the number of open parentheses is always greater than or equal to that of the close parentheses, and the two counts are equal at the end. Find the number of pairs of first and last stamps with which you can print a valid line by appropriately selecting stamps in the process.

Students participating in the ICPC are sitting evenly spaced around a round table for lunch. Each student has one catered lunch box. There are various types of lunch boxes, and not all students necessarily have the same type. The number of the students is even. Thus, for each student, there is exactly one student on the directly opposite seat of the table. The number of lunch boxes of each type is even.

As the lunch box on the seat directly opposite is easily visible, a student may feel envious if it is not of the same type as that student's own. Therefore, you want each pair of students sitting opposite each other to have the same type of lunch boxes. As the number of lunch boxes of each type is even, such an arrangement is always possible. To rearrange the lunch boxes, you repeat the following operation any number of times: select any pair of adjacent students and have them exchange their lunch boxes. Find the minimum number of such operations required to achieve the goal.