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}$$$.

Junwon Kim runs a Vietnamese noodle restaurant in Sharosu-gil, a street near Seoul National University which is home to trendy gourmets.

Junwon sells two kinds of noodles: one with cilantro, and one without. Today, he will cook $$$n$$$ batches of noodles. Junwon has a fixed schedule cooking the noodles, represented by a length-$$$n$$$ string $$$S$$$. If the $$$i$$$-th character of $$$S$$$ is Y, then the $$$i$$$-th dish Junwon cooks will have cilantro. Otherwise, it will not have cilantro.

Since Junwon's restaurant is very famous, $$$n$$$ customers are already waiting in line to experience his ultimate noodles. The customers' preferences are also represented by a length-$$$n$$$ string $$$T$$$. If the $$$i$$$-th character of $$$T$$$ is Y, then the $$$i$$$-th customer wants noodles with cilantro. Otherwise, the $$$i$$$-th customer wants noodles without cilantro.

Junwon has to serve each customer in a first-come-first-serve manner. In this regard, the $$$i$$$-th customer should receive the $$$i$$$-th dish. However, this may violate the preference of the customer. To solve this problem, Junwon installed noodle storage. The noodle storage stores noodles as a stack: you can only access the noodles that were inserted most recently. Junwon will put all cooked noodles right into the noodle storage, and serve the noodles only from the noodle storage. If Junwon decided to serve the noodles from the storage, then he must serve the topmost noodles - he cannot rearrange the noodles in any way after they are added to the stack.

To summarize, when the $$$i$$$-th customer orders noodles, Junwon will cook $$$0$$$ or more batches of noodles, put them in the noodle storage, and then serve the noodle at the top of the noodle storage. Junwon should schedule the cooking in a way such that every customer receives the noodles that they want. Note that Junwon can't cook more than $$$n$$$ noodles.

Today is a bad day for Junwon, because the infamous Jaehyun Koo is the first customer today. Jaehyun is known for his toxic online food reviews, where he sometimes goes so far that the restaurant should stop creating shit problems food and go out of business.

Junwon thinks the quality of his noodles are uneven. Therefore, he wants to know which dishes have a possibility to be served to Jaehyun, while satisfying the condition that every customer receives a menu that they ordered. Please print the sum of indices of dishes that can be served to Jaehyun. Dishes are 1-indexed. If there is no way to serve dishes, output $$$0$$$.

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.

The Goose Kingdom uses $$$n$$$ types of goose coins as their national currency. The $$$i$$$-th type of goose coin has a value of $$$c_i$$$ goose-dollars and a weight of $$$w_i$$$. For all $$$i\ (1 \le i \le n-1)$$$, $$$c_{i+1}$$$ is a multiple of $$$c_i$$$ and $$$c_i \lt c_{i+1}$$$.

You visited Goose Market and bought $$$p$$$ goose-dollars worth of goods. You want to pay the exact price using exactly $$$k$$$ goose coins. You have infinitely many coins of each type, so you don't have to worry about running out of coins.

Write a program to find the minimum and maximum possible total weights of $$$k$$$ coins with total value of $$$p$$$ goose-dollars. If there is no such set of coins, output $$$-1$$$.

A hedgehog graph is a directed graph where each vertex has exactly one outgoing edge and contains exactly one directed cycle of length at least 3 (the graph does not contain a loop or cycle of length 2.) For every edge $$$e = u \rightarrow v$$$ in the hedgehog graph, $$$v$$$ belongs to the aforementioned single directed cycle.

For a vertex $$$v$$$, if there exists an edge $$$v \rightarrow w$$$, we denote the vertex $$$w = next(v)$$$ as the next vertex. This vertex exists and is unique.

Kipa has $$$n$$$ hedgehog graphs with $$$10^6$$$ vertices. Each vertex is numbered from $$$1$$$ to $$$10^6$$$. Kipa is not given the graph directly. Instead, Kipa can ask the following query at most $$$900$$$ times.

• ? v x: Given a vertex $$$v$$$ and a positive integer $$$x$$$, the jury starts at $$$v$$$, moves to the next vertex $$$x$$$ times, and returns the index of the resulting vertex. ($$$1 \le v \le 10^6, 1 \le x \le 5 \times 10^{18}$$$)

Your task is to help Kipa determine the length of the directed cycle for each hedgehog graph.

Wookje is playing the game League of Legends, where two teams of players fight against each other. Each player manages a champion whose status can be represented by two integers: the health $$$h$$$, and the maximum health $$$H$$$. If a champion's health is less than or equal to zero ($$$h \le 0$$$), the champion dies and leaves the game immediately with $$$h = 0$$$. If a champion's health is above the maximum health ($$$h \gt H$$$), then it is adjusted to its maximum health. $$$H$$$ will always be a positive integer.

In a teamfight, the health of the champion may increase or decrease. More specifically, during a teamfight, the champion was subject to $$$n$$$ actions. The $$$i$$$-th ($$$1 \le i \le n$$$) action increases the health of the champion by $$$a_i$$$, subject to the rules above. If $$$a_i$$$ is positive, it means the champion was healed. If $$$a_i$$$ is negative, it means the champion was attacked. If $$$a_i$$$ is zero, then nothing happened to the champion.

Wookje's favorite champion in League of Legends is a lamb named Kindred. Kindred has a ultimate ability named Lamb's Respite. Let's see what this ability does.

Formally, consider a champion with maximum health $$$H$$$. If Wookje activates Lamb's Respite from right before the $$$l$$$-th action until right after the $$$r$$$-th action, a champion's health will never fall below $$$\lceil \frac{H}{10} \rceil$$$ during these actions. If a champion's health was less than or equal to $$$\lceil \frac{H}{10} \rceil$$$ right before the $$$l$$$-th action, or would hypothetically be less than or equal to $$$\lceil \frac{H}{10} \rceil$$$ after the $$$i$$$-th action for some $$$l \le i \le r$$$, then its health is set to $$$\lceil \frac{H}{10} \rceil$$$ and does not change any further until after the $$$r$$$-th action completes. Otherwise, Lamb's Respite does not affect how the champion's health changes.

It is very important to make the right decision on when to activate Lamb's Respite. Wookje wants to improve his decision-making skills. However, the teamfights are too complicated, therefore it's hard for him to know when to activate Lamb's Respite. To help him, please process the following $$$q$$$ queries:

• 1 l r x: The champion's maximum health is $$$x$$$, and its health starts at $$$x$$$. Lamb's Respite is active from right before the $$$l$$$-th action to right after the $$$r$$$-th action. Output the health of the champion after the $$$n$$$ actions. If the champion dies, output $$$0$$$. $$$(1 \le l \le r \le n, 1 \le x \le 10^9)$$$.
• 2 i x: Update $$$a_i$$$ to $$$x$$$. $$$(1 \le i \le n, -10^9 \le x \le 10^9)$$$.

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?

There is a large grid of size $$$n \times m$$$, where each grid cell is either colored or uncolored.

To make some artwork on the grid, Hyunuk wants to put some sheets of colored paper in some of the uncolored cells. Hyunuk selects two integers $$$w, h$$$ where $$$1 \le w \le m, 1 \le h \le n$$$. Then, Hyunuk covers the grid with sheets of colored paper of width $$$w$$$ and height $$$h$$$, satisfying the following conditions.

• The colored paper should exactly cover the grid cells, and not go out of the grid.
• The colored paper cannot be rotated.
• A cell may be covered with more than one sheet of colored paper.
• Every uncolored cell must be covered with at least one sheet of colored paper.
• No colored cell can be covered with any colored paper.

Depending on the selection of width and height, Hyunuk may fail to cover the grid satisfying the above conditions. Please compute the number of possible sheet sizes that can cover the grid satisfying all the above conditions.

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.

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$$$.

To fight the COVID-19 pandemic, vaccines must be transported efficiently to the people. There are $$$n$$$ vaccine manufacturers (numbered from $$$1$$$ to $$$n$$$), $$$m$$$ hospitals (numbered from $$$1$$$ to $$$m$$$), and $$$k$$$ agents (numbered from $$$1$$$ to $$$k$$$) in RUN-land. Agents deliver vaccines from manufacturers to hospitals. The $$$i$$$-th agent has an assignment to deliver $$$c_i$$$ vaccines from manufacturer $$$a_i$$$ to hospital $$$b_i$$$. The assignments are designed such that for any two agents, they must be assigned to different manufacturers or different hospitals, or both.

RUN-land has a very important law: no manufacturer can use more than one agent, and no hospital can receive vaccines from more than one agent. It is possible that not all agents will be called on to complete their assignments.

The agents play an important role in this battle with the pandemic. Therefore, they should be rewarded reasonably based on their merits. The principle known as Vickery-Clarke-Groves pricing states the social value of each agent as follows. Given a set of participating agents $$$S$$$, let $$$f(S)$$$ be the maximum possible count of vaccines delivered to hospitals, subject to the law stated above. Let $$$U$$$ be the set of all agents. Then the social value of each agent $$$e$$$ is $$$f(U) - f(U \setminus \{e\})$$$.

In short, given that the agents always act to maximize the number of vaccines that are delivered, the social value of the agent corresponds to the decrease in the number of vaccines delivered if that agent does not participate.

Please determine the social value for all agents.

You are given an array $$$A$$$, consisting of distinct integers in the range $$$1, 2, \ldots, n$$$.

Let $$$B$$$ be an $$$n \times n$$$ matrix, where $$$B_{i, j} = \min(A_i, \ldots, A_j) \times \max(A_i, \ldots, A_j)$$$ if $$$i \leq j$$$. Otherwise, $$$B_{i, j} = 0$$$.

Given $$$q$$$ queries of the form $$$l, r, s, e$$$, please compute the value $$$\sum_{x = l}^{r}\sum_{y = s}^{e} B_{x, y}$$$ modulo $$$10^9 + 7$$$.