Monocarp has a rectangular sheet of paper that he wants to divide into exactly $$$n$$$ parts.

To do this, he can make two types of cuts:

• A horizontal cut that starts from the left side of the sheet, ends on the right side of the sheet, passing through the entire sheet parallel to the top and bottom sides of the sheet;
• A vertical cut that starts from the top side of the sheet, ends on the bottom side of the sheet, passing through the entire sheet parallel to the left and right sides of the sheet.

Each type of cut can be made an arbitrary number of times. After each cut, none of the resulting pieces of the sheet are moved or removed; each new cut goes through the entire sheet.

Your task is to determine the minimum total number of horizontal and vertical cuts that Monocarp has to make to divide the sheet into exactly $$$n$$$ parts.

There are two screens which can display sequences of uppercase Latin letters. Initially, both screens display nothing.

In one second, you can do one of the following two actions:

• choose a screen and an uppercase Latin letter, and append that letter to the end of the sequence displayed on that screen;
• choose a screen and copy the sequence from it to the other screen, overwriting the sequence that was displayed on the other screen.

You have to calculate the minimum number of seconds you have to spend so that the first screen displays the sequence $$$s$$$, and the second screen displays the sequence $$$t$$$.

Monocarp has balls painted in red, yellow, and green colors; exactly $$$a$$$ red balls, exactly $$$b$$$ yellow balls, and exactly $$$c$$$ green balls.

Monocarp can perform the following operation an arbitrary number of times:

• choose any ball and repaint it in another color: a red ball into yellow or green, a yellow ball into red or green, a green ball into red or yellow.

Your task is to determine the minimum number of operations required to make the number of different colors that the balls are painted equal to two, with the number of balls of each of the two colors being the same.

Adding or removing balls is not allowed.

Monocarp has an array consisting of $$$n$$$ integers, where $$$n$$$ is an even number.

Monocarp has to perform exactly one swap in his array according to the following rules: choose a position $$$x$$$ in the left half of the array ($$$1 \le x \le \frac{n}{2}$$$), choose a position $$$y$$$ in the right half of the array ($$$\frac{n}{2} + 1 \le y \le n$$$), and swap the elements at positions $$$x$$$ and $$$y$$$.

Your task is to determine whether Monocarp can perform exactly one described swap so that the sum of all elements in the left half of the array becomes equal to the sum of all elements in the right half of the array.

Recently, akshiM met a task that needed binomial coefficients to solve. He wrote a code he usually does that looked like this:

    for (int n = 0; n < N; n++) { // loop over n from 0 to N-1 (inclusive)
        C[n][0] = 1;
        C[n][n] = 1;
        for (int k = 1; k < n; k++) // loop over k from 1 to n-1 (inclusive)
            C[n][k] = C[n][k - 1] + C[n - 1][k - 1];
    }

Unfortunately, he made an error, since the right formula is the following:

            C[n][k] = C[n - 1][k] + C[n - 1][k - 1]

But his team member keblidA is interested in values that were produced using the wrong formula. Please help him to calculate these coefficients for $$$t$$$ various pairs $$$(n_i, k_i)$$$. Note that they should be calculated according to the first (wrong) formula.

Since values $$$C[n_i][k_i]$$$ may be too large, print them modulo $$$10^9 + 7$$$.

There's a new game Monocarp wants to play. The game uses a deck of $$$n$$$ cards, where the $$$i$$$-th card has exactly one integer $$$a_i$$$ written on it.

At the beginning of the game, on the first turn, Monocarp can take any card from the deck. During each subsequent turn, Monocarp can take exactly one card that has either the same number as on the card taken on the previous turn or a number that is one greater than the number on the card taken on the previous turn.

In other words, if on the previous turn Monocarp took a card with the number $$$x$$$, then on the current turn he can take either a card with the number $$$x$$$ or a card with the number $$$x + 1$$$.

After Monocarp takes a card on the current turn, it is removed from the deck.

According to the rules of the game, the number of distinct numbers written on the cards that Monocarp has taken must not exceed $$$k$$$.

If, after a turn, Monocarp cannot take a card without violating the described rules, the game ends.

Your task is to determine the maximum number of cards that Monocarp can take from the deck during the game, given that on the first turn he can take any card from the deck.

Monocarp lives in a city, which can be represented as a segment of the number line. The leftmost border of the city is at the point $$$0$$$, and the rightmost border is at the point $$$10^{9}$$$.

There are $$$n$$$ stores in the city. Each store is located at a point with integer coordinate: the $$$i$$$-th store is located at the point $$$a_i$$$. Among the $$$n$$$ stores, there is exactly one store at the point $$$0$$$ and exactly one store at the point $$$10^{9}$$$. There is at most one store at each integer coordinate.

The government has decided to build $$$m$$$ more stores in the city. It is prohibited to build a new store at a point where a store already exists, and at each integer point, at most one new store can be built. It is also prohibited to build stores to the left of point $$$0$$$ and to the right of point $$$10^{9}$$$.

Your task is to choose where to build the new $$$m$$$ stores in such a way that among all $$$(n+m-1)$$$ pairs of neighboring stores, the maximum distance between the stores in a pair is the minimum possible. In other words, you have to minimize the length of the longest segment connecting two neighboring stores.

Let's denote the beauty of a string as follows: consider the lengths of all maximal contiguous blocks consisting of the same letters. Then, the beauty of a string is the sum of the squares of the lengths of all such blocks.

For example, let the string be "aabbbcaaadddd". In this string, the following blocks of identical letters exist: a block of two letters "a", a block of three letters "b", a block of one letter "c", a block of three letters "a", and a block of four letters "d". Thus, the beauty of this string is $$$2^2 + 3^2 + 1^2 + 3^2 + 4^2 = 4 + 9 + 1 + 9 + 16 = 39$$$.

Monocarp has a string $$$s$$$, consisting of $$$n$$$ lowercase Latin letters. He will perform the following action exactly once: choose a pair of adjacent different letters in the string $$$s$$$ and swap them.

Your task is to determine the maximum beauty of the new string that Monocarp can obtain after exactly one swap of adjacent different letters in his string $$$s$$$.

Imagine a game where you play as a character that has two attributes: "Strength" and "Intelligence", that are at zero level initially.

During the game, you'll acquire $$$m$$$ attribute points that allow you to increase your attribute levels — one point will increase one of the attributes by one level. But sometimes, you'll encounter a so-called "Attribute Checks": if your corresponding attribute is high enough, you'll pass it; otherwise, you'll fail it.

Spending some time, you finally prepared a list which contains records of all points you got and all checks you've met. And now you're wondering: what is the maximum number of attribute checks you can pass in a single run if you'd spend points wisely?

Note that you can't change the order of records.

In the most popular card game in Berland, a deck of $$$n \times m$$$ cards is used. Each card has two parameters: suit and rank. Suits in the game are numbered from $$$1$$$ to $$$n$$$, and ranks are numbered from $$$1$$$ to $$$m$$$. There is exactly one card in the deck for each combination of suit and rank.

A card with suit $$$a$$$ and rank $$$b$$$ can beat a card with suit $$$c$$$ and rank $$$d$$$ in one of two cases:

• $$$a = 1$$$, $$$c \ne 1$$$ (a card of suit $$$1$$$ can beat a card of any other suit);
• $$$a = c$$$, $$$b \gt d$$$ (a card can beat any other card of the same suit but of a lower rank).

Two players play the game. Before the game starts, they receive exactly half of the deck each. The first player wins if for every card of the second player, he can choose his card that can beat it, and there is no card that is chosen twice (i. e. there exists a matching of the first player's cards with the second player's cards such that in each pair the first player's card beats the second player's card). Otherwise, the second player wins.

Your task is to calculate the number of ways to distribute the cards so that the first player wins. Two ways are considered different if there exists a card such that in one way it belongs to the first player and in the other way it belongs to the second player. The number of ways can be very large, so print it modulo $$$998244353$$$.

You are given an array $$$a$$$, consisting of $$$n$$$ integers (numbered from $$$1$$$ to $$$n$$$). Initially, they are all zeroes.

You have to process $$$q$$$ queries. The $$$i$$$-th query consists of two different integers $$$x_i$$$ and $$$y_i$$$. During the $$$i$$$-th query, you have to choose an integer $$$p$$$ (which is either $$$x_i$$$ or $$$y_i$$$) and an integer $$$d$$$ (which is either $$$1$$$ or $$$-1$$$), and assign $$$a_p = a_p + d$$$.

After each query, every element of $$$a$$$ should be a non-negative integer.

Process all queries in such a way that the sum of all elements of $$$a$$$ after the last query is the minimum possible.

Monocarp is gathering an army to fight a dragon in a videogame.

The army consists of two parts: the heroes and the defensive artifacts. Each hero has one parameter — his health. Each defensive artifact also has one parameter — its durability.

Before the battle begins, Monocarp distributes artifacts to the heroes so that each hero receives at most one artifact.

The battle consists of rounds that proceed as follows:

• first, the dragon deals damage equal to $$$\frac{1}{a + b}$$$ (a real number without rounding) to each hero, where $$$a$$$ is the number of heroes alive and $$$b$$$ is the number of active artifacts;
• after that, all heroes with health $$$0$$$ or less die;
• finally, some artifacts are deactivated. An artifact with durability $$$x$$$ is deactivated when one of the following occurs: the hero holding the artifact either dies or receives $$$x$$$ total damage (from the start of the battle).

The battle ends when there are no heroes left alive.

Initially, the army is empty. There are $$$q$$$ queries: add a hero with health $$$x$$$ or an artifact with durability $$$y$$$ to the army. After each query, determine the maximum number of rounds that Monocarp can survive if he distributes the artifacts optimally.