Jaehyun likes digits. Among the 10 digits, 6, 7, 8, and 9 are his favorite. Therefore, he made a special card set consisting of only 6, 7, 8 and 9.

Currently, Jaehyun has $$$N\times M$$$ cards. Jaehyun wants to make a magical $$$N$$$ by $$$M$$$ matrix of cards. Each row of the matrix should contain $$$M$$$ cards. He already arranged his cards in a shape of $$$N$$$ by $$$M$$$ matrix.

Figure 1. Initial state, not point symmetric.

To be a magic matrix, the matrix must be point symmetrical: Rotating the matrix 180 degrees results in the same original matrix. For example, 8 is point symmetrical with itself, and 6 and 9 are point symmetrical with each other. Jaehyun doesn't want to switch the position of the cards, so his goal is to make the matrix point symmetrical by only rotating the cards in their original positions.

Figure 2. After rotating two cards, they are point symmetric.

Find the minimum number of cards you have to turn to make a magic matrix.

Sokoban is a famous puzzle game, where the player moves around in the $$$N \times M$$$-size grid, and pushes $$$1 \times 1$$$-size boxes to $$$1 \times 1$$$-size storage locations.

Bigger Sokoban is a possible variation of Sokoban, but the size of boxes and storage locations are bigger than $$$1 \times 1$$$. This problem especially uses $$$2 \times 2$$$ for both.

The rule of Bigger Sokoban is the same as Sokoban. Each square in the grid is an empty square or a wall. Some $$$2 \times 2$$$ area of empty squares contain $$$2 \times 2$$$-size box each and some $$$2 \times 2$$$ area of empty squares are marked as $$$2 \times 2$$$-size storage location each.

The player is in the grid and may move up, down, left, right to the adjacent empty squares, but should not go through walls, boxes, or outside of the grid. If the player tries to move into a box, it is pushed to the adjacent squares in that direction. Boxes must not be pushed to other boxes, walls, or outside of the grid, and they cannot be pulled. The number of boxes is equal to the number of storage locations. The puzzle is solved when all boxes are at the storage locations.

Your mission is to make a Bigger Sokoban grid that needs at least 40,000 moves to solve. To make the situation easier, the grid must satisfy the following constraints:

• $$$1 \leq N, \; M, \; N+M \leq 100$$$.
• The grid contains one box and one storage location.
• The player, the box, and the storage location must not intersect.

Minje operates a game arcade. One of the games is situated in a grid of size $$$N \times M$$$. In each cell, one of the four characters L, R, U, D is written. This denotes the left/right/up/down direction, respectively. A player can freely move inside the grid, but he can NOT move toward the direction written in his cell, or outside of the grid.

Minje cleans the grid after the player enters and leaves the grid. However, cleaning all $$$N \times M$$$ cells is tiring. So Minje wants to only clean the cell which can be possibly visited by the player.

There are $$$Q$$$ players who participated in the game. Minje remembers the first cell and the last cell that each player had stood during the game. These cells are not necessarily at the corner or edge. Please calculate the number of cells which Minje should clean. Every game is independent and does not affect other games' results.

Cki86201 Container Creator (CCC) makes two kinds of containers. One kind of container has 1-ton capacity, and another one has 2-ton capacity. CCC currently has $$$N$$$ containers in a warehouse, which is arranged in a line. To ship the containers, it's good to arrange the containers that are shipped first at the front. Therefore, CCC is going to rearrange those $$$N$$$ containers.

To rearrange the containers we use machines. The machine can pick two or three consecutive containers, and reverse their orders. The cost of using the machine is the total capacity of the selected container plus the base cost $$$C$$$. Therefore, reversing two containers $$$[2, 1]$$$ takes cost $$$3+C$$$, and reversing three containers $$$[1, 1, 2]$$$ takes cost $$$4+C$$$. The number $$$C$$$ is given as an input.

Although this task is trivial to cki86201, he has to play Overwatch now. Please find the way of rearranging the containers using the minimum cost.

Pet graphs are now a popular choice instead of animal pets in Korea. Among them, Trees are the most popular choice of pet graphs, due to their gentle properties and cute outlook. However, Koo is famous for being a maverick in this industry, because he only serves Cactus graphs to customers. Tree and Cactus are certain classes of graphs. A tree is a connected graph without cycles. A cactus is a connected graph, in which there exists no edge which belongs to two distinct cycles. Let's look at the example.

The graph in the first picture is both a tree and a cactus, the graph in the second picture is a cactus, and the graph in the final picture is neither of them. More cycles, more problems.

Koo had been serving Cactus graphs for 21 years with passion and love, but now he is old and tired. Although the popularity of pet graphs increased the visitors in his shop, they rarely became customers because most people considered Cactus graphs to be ugly for their pets. Koo's fortune is declining, and his life is getting tougher. In the end, Koo accepted the grim reality, and he decided to start a tree graph business - by cutting the edges of his lovely cacti.

A graph is a very sensitive creature, so cutting down the middle of the edge makes the whole graph decay. However, if you precisely cut the point where the vertex and the edge meet, the graph can heal itself. Thus, you should remove a whole edge, instead of cutting the middle. Also, you should never cut the graph to be disconnected: It's such a terrible thing to do to the graph.

If you cut the edge $$$e = \{u, v\}$$$, the vertices $$$u, v$$$ will be wounded. A cactus is such a tenacious creature, so it can immediately heal the wounded scars, growing a new edge and a new end vertex. Every edge and vertex has a nonnegative healing factor, which is known to Koo in advance. If an edge $$$e$$$ has a healing factor $$$RE_e$$$, and if an injured vertex $$$v$$$ has a healing factor $$$RV_v$$$, then a new edge of length $$$RE_e + RV_v$$$ will be created in each of the wounded vertices, along with a new vertex in the opposite side of the edge.

In the picture, the red edge is the edge we will cut, and the green edges are the newly created edges.

If we cut exactly one edge from each cycle of a cactus, we can create a tree. Generally, people prefer trees which has a small diameter, where the diameter of the tree is a maximum possible length of some shortest path between the two vertices in the tree. To make a lot of money, Koo wants to cut the cactus and minimize its diameter. Given a cactus, help Koo to find the minimum possible diameter that can be obtained by cutting the edges in the cycle.

Hilbert's hotel has infinitely many rooms, numbered 0, 1, 2, ... At most one guest occupies each room. Since people tend to check-in in groups, the hotel has a group counter variable $$$G$$$.

Hilbert's hotel had a grand opening today. Soon after, infinitely many people arrived at once, filling every room in the hotel. All guests got the group number 0, and $$$G$$$ is set to 1.

Ironically, the hotel can accept more guests even though every room is filled:

• If $$$k$$$ ($$$k \geq 1$$$) people arrive at the hotel, then for each room number $$$x$$$, the guest in room $$$x$$$ moves to room $$$x+k$$$. After that, the new guests fill all the rooms from 0 to $$$k-1$$$.
• If infinitely many people arrive at the hotel, then for each room number $$$x$$$, the guest in room $$$x$$$ moves to room $$$2x$$$. After that, the new guests fill all the rooms with odd numbers.

You have to write a program to process the following queries:

• 1 k - If $$$k \geq 1$$$, then $$$k$$$ people arrive at the hotel. If $$$k = 0$$$, then infinitely many people arrive at the hotel. Assign the group number $$$G$$$ to the new guests, and then increment $$$G$$$ by 1.
• 2 g x - Find the $$$x$$$-th smallest room number that contains a guest with the group number $$$g$$$. Output it modulo $$$10^9 + 7$$$, followed by a newline.
• 3 x - Output the group number of the guest in room $$$x$$$, followed by a newline.

There is a directed graph $$$G$$$ with $$$N$$$ nodes and $$$M$$$ edges. Each node is numbered $$$1$$$ through $$$N$$$, and each edge is numbered $$$1$$$ through $$$M$$$. For each $$$i$$$ ($$$1 \le i \le M$$$), edge $$$i$$$ goes from vertex $$$u_i$$$ to vertex $$$v_i$$$ and has a unique color $$$c_i$$$.

A walk is defined as a sequence of edges $$$e_1$$$, $$$e_2$$$, $$$\cdots$$$, $$$e_{l}$$$ where for each $$$1 \le k \lt l$$$, $$$v_{e_k}$$$ (the tail of edge $$$e_k$$$) is the same as $$$u_{e_{k+1}}$$$ (the head of edge $$$e_{k+1}$$$). We can say a walk $$$e_1, e_2, \cdots, e_l$$$ starts at vertex $$$u_{e_1}$$$ and ends at vertex $$$v_{e_l}$$$. Note that the same edge can appear multiple times in a walk.

The color sequence of a walk $$$e_1, e_2, \cdots, e_l$$$ is defined as $$$c_{e_1}, c_{e_2}, \cdots, c_{e_l}$$$.

Consider all color sequences of walks of length at most $$$10^{100}$$$ from vertex $$$S$$$ to vertex $$$T$$$ in $$$G$$$. Write a program that finds the lexicographically minimum sequence among them.

Maximizer has two permutations $$$A=[a_1,a_2,\cdots,a_N]$$$ and $$$B=[b_1,b_2,\cdots,b_N]$$$. Both $$$A, B$$$ have length $$$N$$$ and consists of distinct integers from $$$1$$$ to $$$N$$$.

Maximizer wants to maximize the sum of differences of each element, $$$\sum_{i=1}^{N} |a_i - b_i|$$$. But he can only swap two adjacent elements in $$$A$$$. Precisely, he can only swap $$$a_i$$$ and $$$a_{i+1}$$$ for some $$$i$$$ from $$$1$$$ to $$$N-1$$$. He can swap as many times as he wants.

What is the minimum number of swaps required for maximizing the difference sum?

You are given a simple connected undirected weighted graph $$$G$$$ with $$$N$$$ nodes and $$$M$$$ edges. Each node is numbered 1 through $$$N$$$.

A spanning tree of $$$G$$$ is a subgraph of $$$G$$$, which is a tree and connects all the vertices of $$$G$$$. The diameter of a tree is the length of the longest path among the paths between any two nodes in the tree. A minimum diameter spanning tree of $$$G$$$ is a spanning tree of $$$G$$$ that has a minimum diameter.

Write a program that finds any minimum diameter spanning tree.

Figure 1. Gapcheon and an Expo bridge in a cloudy day

Gapcheon is a stream that flows through the Daedeok Innopolis: A research district in Daejeon which includes KAIST, Expo Science Park, National Science Museum, among many others. The waterfront of Gapcheon is used as a park, which is a facility for leisure and recreation.

In this problem, we model the Gapcheon as a slightly curved arc. In the arc, there are exactly $$$10^6$$$ points marked by each centimeter. In Gapcheon, there are $$$N$$$ bridges that connect two distinct points in the arc in a straight line segment. Such a line segment may touch other segments in an endpoint but never crosses them otherwise. For each pair of points, there exists at most one bridge that directly connects those two points.

Figure 2. $$$x, y, z$$$ are bridges that do not cross but only touch each other in an endpoint. This can be a possible input instance. Points with number $$$8 \ldots 10^6$$$ are omitted for brevity.

Figure 3. $$$x, y$$$ are bridges that cross each other. This is not a possible input instance. Points with number $$$8 \ldots 10^6$$$ are omitted for brevity.

The city council is planning to place some lights in the bridges, to make Gapcheon as a more enjoyable place in the night. For each bridge, the city council calculated the aesthetical value if the lights are installed in these bridges. These value can be represented as a positive integer.

However, too many lightings will annoy the residents at midnight. To address this issue, the council decided to make some regulations: for every arc between two adjacent points, there should be at most $$$k$$$ lighted bridges visible from there. We call a line segment visible from an arc connecting $$$i, i+1$$$, when one endpoint of the segment has an index at most $$$i$$$, and another endpoint of the segment has an index at least $$$i+1$$$.

The city council wants to consider the tradeoff between light pollution and the night view, so you should provide the maximum possible sum of aesthetical value, for all integers $$$1 \le k \le N$$$.

The original title of this problem is "Tree Product Metric Voronoi Diagram Query Without One Point".

You are given two weighted trees $$$T_1,\ T_2$$$ of size $$$N$$$, where each vertex are labeled with numbers $$$1 \ldots N$$$. Let $$$dist(T_1,\ i,\ j)$$$ be the total weight of the shortest path from node $$$i$$$ to $$$j$$$ in tree $$$T_1$$$, and define $$$dist(T_2,\ i,\ j)$$$ similarly.

Consider a point set of size $$$N$$$. Similar to Manhattan metric (in fact, this is a generalization of it), we can define the distance between two points $$$1 \le i,\ j \le N$$$: It is the sum of two distances, $$$dist(T_1,\ i,\ j) + dist(T_2,\ i,\ j)$$$. For each $$$1 \le i \le N$$$, please determine the "closest point" from the point $$$i$$$. Formally, for each $$$i$$$, you should find $$$min_{j \neq i}{dist(T_1,\ i,\ j) + dist(T_2,\ i,\ j)}$$$.