Consider the histogram composed of $$$n$$$ squares with side lengths $$$a_1, a_2, \cdots, a_n$$$. Let's call the sequence $$$(a_1, a_2, \cdots, a_n)$$$ the histogram sequence of this histogram.

Let's consider the height of each column in this histogram. The first $$$a_1$$$ columns will each have height $$$a_1$$$, the following $$$a_2$$$ columns will each have height $$$a_2$$$, ... and the last $$$a_n$$$ columns will each have height $$$a_n$$$. Now, let us define the height sequence $$$(b_1, b_2, \cdots, b_{a_1 + a_2 + \cdots + a_n})$$$ where $$$b_j\ (1 \le j \le a_1+a_2+\cdots+a_n)$$$ is the height of the $$$j$$$-th column.

For example, the histogram with $$$(3, 2, 1, 4)$$$ as its histogram sequence has $$$(3, 3, 3, 2, 2, 1, 4, 4, 4, 4)$$$ as its height sequence.

Write a program to find the histogram sequence given the height sequence.

A farm is divided into $$$n \times n$$$ unit squares of $$$n$$$ rows and $$$n$$$ columns. Let's define $$$(i, j)$$$ as the unit square in the $$$i$$$-th row and the $$$j$$$-th column ($$$1 \le i \le n$$$, $$$1 \le j \le n$$$).

The distance between two squares $$$(i_1, j_1)$$$ and $$$(i_2, j_2)$$$ is defined to be $$$d\left(\left(i_1, j_1\right), \left(i_2, j_2\right)\right) = |i_1 - i_2| + |j_1 - j_2|$$$, the Manhattan distance between those two squares.

There are automatic sprayers on this farm that spray fertilizer solution or herbicide so that the owner can produce grain efficiently.

Each sprayer lies entirely in a unit square. The sprayer in $$$(x,y)$$$ sprays $$$A_{x,y}$$$ liters of solution to all unit squares. $$$A_{x,y}$$$ can be any nonnegative integer.

The energy required for the sprayer in $$$(x, y)$$$ to spray solution to $$$(i, j)$$$ is exactly $$$d((x, y), (i, j)) \times A_{x,y}$$$. For each square $$$(i, j)$$$, we compute $$$E_{i,j}$$$, the sum of energies needed for all sprayers to spray the square $$$(i, j)$$$.

Given the matrix $$$E$$$, write a program that generates any possible matrix $$$A$$$ that corresponds to matrix $$$E$$$. $$$E$$$ will be given such that there exists such a matrix $$$A$$$ of nonnegative integers whose sum is at most $$$10^{12}$$$.

Byteazar calls the positive integer beautiful if the sum of its digits is equal to 10. Byteazar got $$$n$$$ cards, each card containing one digit between 1 and 9, inclusively, on the face.

Count the maximal number of the beautiful numbers that can be built from the given cards simultaneously, i.e. that any card can be used in no more than one integer.

For example, if we have the cards with digits 1,9,9,7,9,3, we can build two beautiful numbers: first with the digits 1 and 9 and second with the digits 7 and 3. From cards 1,1,1,1,1,1,1,1,1,2,8 we can build only one beautiful number (use 8 and 2, or two ones and 8, or eight ones and 2). From the set of cards 4, 5, 7 we cannot build any beautiful number.

You are planning to construct a water pipeline network, connecting $$$n$$$ buildings in KAIST. Due to budget problems, you can only use $$$n-1$$$ pipes. Each pipe is undirected and connects two different buildings, and all $$$n$$$ buildings must be pairwise connected through some sequence of pipes. These pipes form a network.

As a careful planner, you designed $$$d$$$ different networks and want to compare them. One can describe each pipe in the network with a durability, which is a single positive integer. Given a network $$$T$$$, define the vulnerability $$$v_{T}(i, j)$$$ of two distinct buildings $$$i$$$ and $$$j$$$ to be the minimum durability of a pipe whose removal separates buildings $$$i$$$ and $$$j$$$. In other words, $$$v_{T}(i, j)$$$ is the minimum durability over all pipes on the path connecting $$$i$$$ to $$$j$$$.

If two networks $$$T_{1}$$$ and $$$T_{2}$$$ satisfy $$$v_{T_1}(i, j) = v_{T_2}(i, j)$$$ for all $$$1 \le i \lt j \le n$$$, we say $$$T_{1}$$$ and $$$T_{2}$$$ are equivalent. To filter out unnecessary plans, group the $$$d$$$ designs up to equivalency.

Joon-Pyo decorated a flowerbed in front of his home. The flowerbed is in the shape of an $$$n \times m$$$ grid, and one flower is planted in each cell. There are 26 colors, one corresponding to each uppercase letter from A to Z. Suddenly, he wanted to redecorate the flowerbed.

1. Place the equipment so that exactly the flowers in the first $$$d$$$ rows and the first $$$d$$$ columns are inside.
2. Rotate the $$$d \times d$$$ square inside the equipment $$$90^\circ$$$ clockwise. If this square contains flowers from the last $$$d$$$ rows and the last $$$d$$$ columns, then the construction is finished. Otherwise, if this square does not contain flowers in the last $$$d$$$ columns, move the equipment $$$x$$$ squares to the right. Otherwise, move the equipment down by $$$y$$$ squares and all the way to the left so it contains flowers from the first $$$d$$$ columns.
3. Repeat step 2 until construction is finished.

Note that the equipment will never go out of the flowerbed, as $$$x$$$, $$$y$$$, and $$$d$$$ are carefully determined before construction begins.

He cannot start construction without knowing the outcome. Write a program that outputs the result.

There are $$$n$$$ cities in Byteland and $$$n-1$$$ bidirectional highways connecting those cities such as each highway connects exactly two distinct cities and that it is possible to travel between any two cities using one or several highways. For each highway, its length $$$l_i$$$ is known.

Byteazar is the road inspector. He plans to check all highways in the country. Byteazar is very experienced, so she can inspect the highway just by visiting any of the two cities connected by that highway. Of course, Byteazar moves between cities using the highway network.

Byteazar starts in city 1. Calculate the minimum summary distance for Byteazar to check all the highways in the Byteland.

We are developing the Or Machine, a computer heavily optimized solely for one kind of operation: the |= operator in C++'s term.

The Or Machine has $$$n$$$ registers, each containing a nonnegative integer less than $$$2^8$$$. We label them $$$x_1, x_2, \cdots, x_n$$$. A program is represented by a list of $$$l$$$ operations. Each operation is represented by a pair of integers $$$(a, b)$$$, meaning that the machine should update $$$x_a$$$ with the bitwise OR of $$$x_a$$$'s and $$$x_b$$$'s values.

The Or Machine takes a program, the initial values of the registers, and a positive integer $$$t$$$. When run, the program performs each operation in the program one by one. When the last operation is performed, it goes back to the first operation and repeats the process. The machine stops after performing exactly $$$t$$$ operations.

We want our machine to be much faster than general-purpose computers, and hardware optimization is probably not enough. Can you help us with some software optimization?

Hitagi has a ruler of infinite length. It has a mark on every integer, where the mark on integer $$$i$$$ has color $$$c_i$$$. Each color is represented by an integer from $$$1$$$ to $$$100$$$.

She noticed that the ruler's color pattern repeats with a period of $$$t$$$. The period $$$t$$$ is defined by the smallest positive integer that satisfies $$$c_i = c_{i+t}$$$ for all integers $$$i$$$.

Hitagi told Koyomi the colors of $$$n$$$ marks of her choice. Koyomi wants to find all positive integers that cannot be a period of the ruler, regardless of the colors of unchosen marks. Write a program to find all such numbers, and output their count and sum.

Bytica is playing the solitaire game based on the well-known Cities game.

In the solitaire version, you have the list of $$$n$$$ city names, and your goal is to arrange them in sequence such as for any $$$1 \le i \lt n$$$ the last letter of $$$i$$$-th word is the first letter of $$$i+1$$$-st word, and the last letter of the $$$n$$$-th word is the first letter of the first word.

Given the list of city names, prepared by Bytica, check if she can reach the goal of the solitaire game.

Last month, $$$n$$$ people participated in three competitions. The people are labeled with distinct integers from $$$1$$$ to $$$n$$$. In each competition, the people were sorted by performance and got ranked from $$$1$$$ to $$$n$$$. The lower the rank, the better the player. There were no ties in any of the rankings.

Today, instead of $$$n$$$ people participating at once, two people compete head-to-head. The winner of the match is the person who wins at least two out of three competitions. The winner then proceeds to compete with another person. This turned out to be quite interesting: even if a person $$$a$$$ cannot directly win against another person $$$b$$$, it's possible that another person $$$c$$$ wins against $$$b$$$ and then $$$a$$$ wins against $$$c$$$. That way, we can say that $$$a$$$ "indirectly" wins against $$$b$$$. It's also possible that two people can indirectly win against each other!

Formally, a person $$$a$$$ is said to directly win against another person $$$b$$$ if $$$a$$$ has a lower rank than $$$b$$$ in at least two competitions. Also, $$$a$$$ is said to indirectly win against $$$b$$$ if there exists a sequence of people $$$p_1, p_2, \cdots, p_k$$$ ($$$k \geq 2$$$) such that $$$p_i$$$ directly wins against $$$p_{i+1}$$$ for all $$$i = 1, \cdots, k-1$$$, $$$p_1 = a$$$ and $$$p_k = b$$$.

Given the ranks of the people in each competition, answer $$$q$$$ questions asking whether person $$$a$$$ indirectly wins against another person $$$b$$$.

Hyunuk has a long barrel of $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) cells. Each cell is either empty or contains a bead. When storing beads, it doesn't look good if they are scattered here and there, so Hyunuk wants to gather all the beads at one end. Specifically, if the barrel has $$$k$$$ beads, the beads must be in cells $$$1$$$ through $$$k$$$ or in cells $$$n-k+1$$$ through $$$k$$$.

Hyunuk can move the bead in the $$$i$$$-th cell of the barrel to the ($$$i-1$$$)-th cell or the ($$$i+1$$$)-th cell by lightly pushing it. If there is a bead in the cell to be moved, that bead is also pushed in the same direction. For example, let there be beads in the 2nd, 3rd, and 5th cells. If Hyunuk pushes the bead in the 2nd cell to the 3rd cell, the bead in the 3rd cell is also pushed to the 4th cell. The bead in the 5th cell remains in place.

Hyunuk wonders how the minimum number of moves required to organize all beads will change when he adds or removes beads from the barrel. Write a program that calculates the minimum number of moves required to organize the bead barrel as Hyunuk inserts or removes beads from the barrel.